回文大师

回文大师

关键

1.正着处理，因为题目要求是倒着相同，所以倒着进行匹配就可以了，这个真的是惊艳到我了。
2.正常思路的KMP是很难处理的，但是这里是能匹配多长，就把多长的给计算上就可以了。
3.然后就是答案的计算，不是找所有的子串，而是从i开头后的最大的长度，也就是如果[1,2]可以，那么不能再计算一次[1,1]，只能取最大的长度
所以不能直接相加，而是采用类似于数的模式，f(nei)+=f(i)，从后面向前面进行递推，从而加上所有的前缀，又保证只加了一次

代码

#include <bits/stdc++.h>
using namespace std;
const int M=1e6+5;

int a[M],ne[M],f[M];

int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=2,j=0;i<=n;i++) {
        while(j&&a[i]!=a[j+1])j=ne[j];
        if(a[i]==a[j+1])j++;
        ne[i]=j;
    }
    for(int i=n,j=0;i>=1;i--) {
        while(j&&a[i]!=a[j+1])j=ne[j];
        if(a[i]==a[j+1])j++;
        f[j]++;
    }
    for(int i=n;i>=1;i--)f[ne[i]]+=f[i];
    for(int i=1;i<=n;i++)cout<<f[i]<<' ';
    return 0;
}
//倒着进行匹配就可以了