题意:给一个长度不超过1000的字符串,从中间切开前缀后缀(各至少一个字符),问每个切法中前缀后缀的相同的子串对的个数。
重新理解后缀自动机。
1.后缀自动机里面,endpos表示这个节点作为结束位置出现的次数。一个maxlen更长的节点出现意味着它的link也一定出现。只属于p节点的本质不同的子串种类是maxlen[p]-maxlen[link[p]]。
2.在后缀自动机里面跑另一个字符串的时候,每次往下走的时候匹配的长度要像下面那样处理。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1000 + 5;
const int MAXNODE = MAXN * 2 + 5;
//SuffixAutomaton
struct SAM {
int ch[MAXNODE][26];
int link[MAXNODE];
int maxlen[MAXNODE];
int endpos[MAXNODE];
ll sum[MAXNODE];
void NewNode(int x, int l = 0) {
memset(ch[x], 0, sizeof(ch[x]));
link[x] = 0;
maxlen[x] = l;
endpos[x] = 1;
sum[x] = 0;
}
void CopyNewNode(int x, int y, int l) {
memcpy(ch[x], ch[y], sizeof(ch[x]));
link[x] = link[y];
maxlen[x] = l;
endpos[x] = 0;
sum[x] = 0;
}
const int root = 1;
int top, last; //top为节点个数,last末尾节点的位置
void Init() {
NewNode(1);
top = 1, last = 1;
}
void Extend(char _c) {
int c = _c - 'a';
int p = last, x = last = ++top;
NewNode(x, maxlen[p] + 1);
while(p && !ch[p][c]) {
ch[p][c] = x;
p = link[p];
}
if(!p)
link[x] = 1;
else {
int q = ch[p][c];
if(maxlen[p] + 1 == maxlen[q])
link[x] = q;
else {
int y = ++top;
CopyNewNode(y, q, maxlen[p] + 1);
link[q] = link[x] = y;
while(p && ch[p][c] == q) {
ch[p][c] = y;
p = link[p];
}
}
}
}
int cnt[MAXN];
int rnk[MAXNODE];
void UpdateLink() {
memset(cnt, 0, sizeof(cnt[0]) * (top + 1));
for(int i = 1; i <= top; ++i)
++cnt[maxlen[i]];
for(int i = 1; i <= top; ++i)
cnt[i] += cnt[i - 1];
for(int i = 1; i <= top; ++i)
rnk[cnt[maxlen[i]]--] = i;
for(int i = top; i >= 1; --i) {
int x = rnk[i];
endpos[link[x]] += endpos[x];
}
for(int i = 1; i <= top; ++i) {
int x = rnk[i];
sum[x] = sum[link[x]] + 1ll * endpos[x] * (maxlen[x] - maxlen[link[x]]);
}
}
ll Calc(char *t) {
int p = 1;
ll ans = 0;
int tlen = 0;
int n = strlen(t);
for(int i = 0; i < n; ++i) {
int c = t[i] - 'a';
if(ch[p][c]) {
//从这个节点走下去,继续+1
++tlen;
p = ch[p][c];
} else {
while(p && !ch[p][c])
p = link[p];
if(p) {
//root->的路径p是不是t当前匹配的子串呢?
//从这个节点走下去,等于当前子串的len+1,而不一定等于下面的maxlen
tlen = maxlen[p] + 1;
p = ch[p][c];
} else {
tlen = 0;
p = 1;
}
}
ans += sum[link[p]] + endpos[p] * (tlen - maxlen[link[p]]);
}
return ans;
}
} sam;
char s[MAXN], t[MAXN];
ll ans[MAXN];
int main() {
#ifdef Yinku
freopen("Yinku.in", "r", stdin);
#endif // Yinku
scanf("%s", s);
int sn = strlen(s);
for(int m = 1; m < sn; ++m) {
sam.Init();
for(int i = 0; i < m; ++i)
sam.Extend(s[i]);
sam.UpdateLink();
for(int j = m; j <= sn; ++j)
t[j - m] = s[j];
ans[m] = sam.Calc(t);
}
int T;
scanf("%d", &T);
while(T--) {
int m;
scanf("%d", &m);
printf("%lld
", ans[m]);
}
}