Parco_Love_String - 秒客网

二维的kmp直接搞出来emmm，后缀自动机都没这个快（本弱鸡不会后缀自动机）
#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define re register

const int N=;

void read(int &a)

{

    a=;

    int d=;

    char ch;

    while(ch=getchar(),ch>''||ch<'')

        if(ch=='-')

            d=-;

    a=ch-'';

    while(ch=getchar(),ch>=''&&ch<='')

        a=a*+ch-'';

    a*=d;

}

void write(int x)

{

    if(x<)

        putchar(),x=-x;

    if(x>)

        write(x/);

    putchar(x%+'');

}

char s[N];

int g[N][N],ans[N],n,T,f[N][N];

int main()

{

    scanf("%s",s+);

    n=strlen(s+);

    for(re int i=;i<=n;i++)

        for(re int j=;j<=n;j++)

            if(s[i]==s[j])///相等就将前面的转移过来+1，算二维的KMP

                f[i][j]=f[i-][j-]+;

    for(re int i=n;i>=;i--)

        for(re int j=n;j>=;j--)

            if(s[i]==s[j])///同理

                g[i][j]=g[i+][j+]+;

    for(re int i=;i<=n;i++)///i=1只有一个字母，那么相同字母出现的个数就是答案

        if(s[]==s[i])

            ans[]++;

    for(re int i=;i<=n;i++)

    {

        ans[i]=ans[i-];/// 上一个i分割的答案肯定我这个一个i也有（子串--）

        for(re int j=i+;j<=n;j++)///算出从这个分割点开始后的所有答案

            ans[i]+=min(f[i][j],j-i);

        for(re int j=;j<i;j++)///把前面一个串自己相同的子串删除，因为自己不能跟自己比较

            ans[i]-=min(g[i][j],i-j);

    }

    read(T);

    while(T--)

    {

        int x;

        read(x);

        write(ans[x]);

        putchar('\n');

    }

    return ;

}