- Palindromic characteristics of string s with length |s| is a sequence of |s|integers, where k-th number is the total number of non-empty substrings of s which are k-palindromes.
- A string is 1-palindrome if and only if it reads the same backward as forward.
- A string is k-palindrome (k>1) if and only if:
Its left half equals to its right half.
- Its left and right halfs are non-empty (k-1)-palindromes.
- The left half of string t is its prefix of length |t|/2, and right half - the suffix of the same length. |t|/2 denotes the length of string t divided by 2, rounded down.
- Note that each substring is counted as many times as it appears in the string. For example, in the string "aaa" the substring "a" appears 3 times.
- Input
- The first line contains the string s (1≤|s|≤5000) consisting of lowercase English letters.
- Output
- Print |s| integers - palindromic characteristics of string s.
- Examples
- Input
- abba
- Output
- 6 1 0 0
- Input
- abacaba
- Output
- 12 4 1 0 0 0 0
- Note
In the first example 1-palindromes are substring «a», «b», «b», «a», «bb», «abba», the substring «bb» is 2-palindrome. There are no 3- and 4-palindromes here.
题意:
给定一个字符串, 定义字符串的等级如下:
如果一个字符串是回文串, 那么等级为 1
如果他的左半边的字符串和右半边的字符串也都是回文串, 那么等级为 2.
如果他左半边的左半边和右半边是回文串, 右边同, 那么等级为 3.
以此类推.....
让求这个字符串的所有连续子串的等级情况,
你只需要输出等级为 1~n 的子串的个数就 ok 了.
思路:
用区间 DP,n*n 处理字符串, 即 dp[i][j] =1 则代表字符串 s 中, s[i~j] 是一个回文串.
而数组 f[i][j] 代表 s[i~j] 的等级.
细节见代码, 有详细的注释.
- #include <iostream>
- #include <cstdio>
- #include <cstring>
- #include <algorithm>
- #include <cmath>
- #include <queue>
- #include <stack>
- #include <map>
- #include <set>
- #include <vector>
- #include <iomanip>
- #define ALL(x) (x).begin(), (x).end()
- #define dll(x) scanf("%I64d",&x)
- #define xll(x) printf("%I64d\n",x)
- #define sz(a) int(a.size())
- #define all(a) a.begin(), a.end()
- #define rep(i,x,n) for(int i=x;i<n;i++)
- #define repd(i,x,n) for(int i=x;i<=n;i++)
- #define pii pair<int,int>
- #define pll pair<long long ,long long>
- #define gbtb iOS::sync_with_stdio(false),cin.tie(0),cout.tie(0)
- #define MS0(X) memset((X), 0, sizeof((X)))
- #define MSC0(X) memset((X), '\0', sizeof((X)))
- #define pb push_back
- #define mp make_pair
- #define fi first
- #define se second
- #define eps 1e-6
- #define gg(x) getInt(&x)
- #define db(x) cout<<"== ["<<x<<"] =="<<endl;
- using namespace std;
- typedef long long ll;
- ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
- ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
- ll powmod(ll a,ll b,ll MOD){ll ans=1ll;while(b){if(b&1)ans=ans*a%MOD;a=a*a%MOD;b>>=1;}return ans;}
- inline void getInt(int* p);
- const int maxn=1000010;
- const int inf=0x3f3f3f3f;
- /*** TEMPLATE CODE * * STARTS HERE ***/
- char s[maxn];
- int cnt[maxn];
- const int N = 5e3+7;
- int dp[N][N];
- int f[N][N];
- int main()
- {
- // freopen("C:\\Users\\DH_M\\Desktop\\code_io\\in.txt.txt","r",stdin);
- // freopen("C:\\Users\\DH_M\\Desktop\\code_io\\out.txt.txt","w",stdout);
- scanf("%s",s+1);
- int len=strlen(s+1);
- repd(i,1,len)
- {
- dp[i][i]=dp[i][i-1]=1;// dp[i][i] 长度为 1 的字符串肯定是回文串, 而 dp[i][i-1]=1 是因为在区间 DP 转移的时候要用到.
- f[i][i]=1;// 长度为 1 的串肯定只能是 1 等级的字符串
- }
- cnt[1]+=len;// len 个长度为 1 的字符串加到等级为 1 的中
- repd(k,2,len)// k 这里是枚举子串的长度
- {
- // len = 5
- // 1 2 3 4 5
- // 1 5
- // 1 2
- repd(i,1,len+1-k)
- {
- int j=i+k-1;// 区间的左区间
- dp[i][j]=dp[i+1][j-1]&(s[i]==s[j]);// 转移过程用到的 "与" 运算
- // 因为 s[i]~s[j] 想要是回文串, 那么要在 s[i+1]~s[j-1] 是回文串的基础上, s[i]==s[j]
- // 这里长度为 2 的时候就要用到 dp[i][i-1]=1
- f[i][j]=dp[i][j] ? f[i][(i+j-1)/2]+1:0;// 等级转移,
- // 首先判断是不是回文串, 如果不是, 等级只能为 0
- // 如果是回文串, 那么这个字符串的等级为他的左半边字符串的等级 + 1
- cnt[f[i][j]]++;// 在答案数组中加一下
- }
- }
- for(int i=len;i>=1;i--)
- {
- cnt[i]+=cnt[i+1];// 处理下答案数组, 因为 i+1 等级的字符串一定也满足 i 等级
- }
- repd(i,1,len)
- {
- printf("%d",cnt[i] );// 输出答案
- }
- // Input
- // abba
- // Output
- // 6 1 0 0
- return 0;
- }
- inline void getInt(int* p) {char ch;do {ch = getchar();}
- while (ch == '' || ch =='\n');if (ch =='-') {*p = -(getchar() -'0');
- while ((ch = getchar())>= '0' && ch <= '9') {*p = *p * 10 - ch + '0';}}
- else {*p = ch - '0';while ((ch = getchar())>= '0' && ch <= '9')
- {*p = *p * 10 + ch - '0';}}}
来源: http://www.bubuko.com/infodetail-2970214.html