hdu6599 I Love Palindrome String
14205 ワード
例から分かるように,問題で求めた回文列の数は,本質的に異なる回文列の数であり,これは直接回文ツリーで行うことができる.
前半が回文列という制限を考えると、これは回文木がやりにくいので、もう1つのマラ車をセットして、回文木のノードに挿入された最後の文字の位置を記録して、マラ車を使ってこの前半が回文列かどうかをすばやく判断することができます.
転載先:https://www.cnblogs.com/hyfer/p/11575134.html
前半が回文列という制限を考えると、これは回文木がやりにくいので、もう1つのマラ車をセットして、回文木のノードに挿入された最後の文字の位置を記録して、マラ車を使ってこの前半が回文列かどうかをすばやく判断することができます.
#include
#include
#include <string>
#include
#include
#include
#include
#include
#define fo(i, l, r) for (int i = l; i <= r; i++)
#define fd(i, l, r) for (int i = r; i >= l; i--)
#define mem(x) memset(x, 0, sizeof(x))
#define ll long long
using namespace std;
const int maxn = 300050;
ll read()
{
ll x = 0, f = 1;
char ch = getchar();
while (!(ch >= '0' && ch <= '9'))
{
if (ch == '-')
f = -1;
ch = getchar();
};
while (ch >= '0' && ch <= '9')
{
x = x * 10 + (ch - '0');
ch = getchar();
};
return x * f;
}
char Ma[maxn * 2];
int Mp[maxn * 2];
void Manacher(char s[], int len)
{
int l = 0;
Ma[l++] = '$';
Ma[l++] = '#';
for (int i = 0; i < len; i++)
{
Ma[l++] = s[i];
Ma[l++] = '#';
}
Ma[l] = 0;
int mx = 0, id = 0;
for (int i = 0; i < l; i++)
{
Mp[i] = mx > i ? min(Mp[2 * id-i], mx-i) : 1;
while (Ma[i + Mp[i]] == Ma[i-Mp[i]])
Mp[i]++;
if (i + Mp[i] > mx)
{
mx = i + Mp[i];
id = i;
}
}
}
const int N = 300010, S = 26;
int all, son[N][S], fail[N], cnt[N], len[N], text[N], pos[N], last, tot;
int newnode(int l)
{
for (int i = 0; i < S; i++)
son[tot][i] = 0;
cnt[tot] = 0, len[tot] = l;
return tot++;
}
void init()
{
last = tot = all = 0;
newnode(0), newnode(-1);
text[0] = -1, fail[0] = 1;
}
int getfail(int x)
{
while (text[all - len[x] - 1] != text[all])
x = fail[x];
return x;
}
void add(int w,int p)
{
text[++all] = w;
int x = getfail(last);
if (!son[x][w])
{
int y = newnode(len[x] + 2);
fail[y] = son[getfail(fail[x])][w];
son[x][w] = y;
pos[y] = p;
}
cnt[last = son[x][w]]++;
}
void count()
{
for (int i = tot - 1; ~i; i--)
cnt[fail[i]] += cnt[i];
}
char s[maxn];
int slen, s2[maxn];
ll ans[maxn];
int flag;
inline bool check(int l,int r){
int len = r-l+1;
if(len==1)return true;
r = (l+r)>>1;
len = r-l+1;
if(len&1){
int t = l + (len>>1);
t *= 2;
return Mp[t]-1 >= len;
}else{
int t = l + (len >> 1);
t = t*2-1;
return Mp[t]-1 >= len;
}
}
void dfs(int u, int d)
{
fo(i, 0, 25)
{
if (son[u][i])
{
s2[d + 1] = i;
dfs(son[u][i], d + 1);
}
}
if (d)
{
int lenu = d + d - flag;
int rp = pos[u];
int lp = pos[u]-lenu+1;
if(check(lp,rp))ans[d + d - flag] += cnt[u];
}
}
int main()
{
int tt = 0;
int T;
while (scanf("%s", s + 1) != EOF)
{
init();
memset(ans, 0, sizeof(ans));
slen = strlen(s + 1);
fo(i, 1, slen)
{
add(s[i] - 'a',i);
}
count();
Manacher(s+1,slen);
flag = 0;
dfs(0, 0);
flag = 1;
dfs(1, 0);
printf("%lld", ans[1]);
fo(i, 2, slen)
{
printf(" %lld", ans[i]);
}
putchar('
');
}
return 0;
}
転載先:https://www.cnblogs.com/hyfer/p/11575134.html