二维的kmp直接搞出来emmm， 后缀自动机都没这个快（本弱鸡不会后缀自动机）
#include <bits/stdc++.h> using namespace std; #define ll long long #define re register const int N=1010; void read(int &a) { a=0; int d=1; char ch; while(ch=getchar(),ch>'9'||ch<'0') if(ch=='-') d=-1; a=ch-'0'; while(ch=getchar(),ch>='0'&&ch<='9') a=a*10+ch-'0'; a*=d; } void write(int x) { if(x<0) putchar(45),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); } char s[N]; int g[N][N],ans[N],n,T,f[N][N]; int main() { scanf("%s",s+1); n=strlen(s+1); for(re int i=1;i<=n;i++) for(re int j=1;j<=n;j++) if(s[i]==s[j])///相等就将前面的转移过来+1，算二维的KMP f[i][j]=f[i-1][j-1]+1; for(re int i=n;i>=1;i--) for(re int j=n;j>=1;j--) if(s[i]==s[j])///同理 g[i][j]=g[i+1][j+1]+1; for(re int i=2;i<=n;i++)///i=1只有一个字母，那么相同字母出现的个数就是答案 if(s[1]==s[i]) ans[1]++; for(re int i=2;i<=n;i++) { ans[i]=ans[i-1];/// 上一个i分割的答案肯定我这个一个i也有（子串--） for(re int j=i+1;j<=n;j++)///算出从这个分割点开始后的所有答案 ans[i]+=min(f[i][j],j-i); for(re int j=1;j<i;j++)///把前面一个串自己相同的子串删除，因为自己不能跟自己比较 ans[i]-=min(g[i][j],i-j); } read(T); while(T--) { int x; read(x); write(ans[x]); putchar(' '); } return 0; }