hdu6629 题目描述 给你一个字符串 然后求从任意位置开始的后缀与原串匹配的最大长度+1的总和 好像是扩展kmp的模板题 但是做这个题目的时候没有学过扩展kmp 就想了想 然后看数据 应该是需要O(n)处理完的 然后如果纯粹暴力的 其实会有很多无用的匹配 想了想马拉车记录最大匹配和最大匹配对应节点的思想，把它魔改了一下（还是要记录最大匹配节点和最大匹配，但是改了下对应关系），A掉了，具体看代码。
#include<bits/stdc++.h> typedef long long ll; using namespace std; const int maxn=1e6+50; char s[maxn]; int p[maxn]; //p[i]以i为初始位置的后缀与原串的最长公共前缀的长度+1 ll ans; void solve() { int l=strlen(s); int id,mx=-1;//mx为当前能匹配到字符串的最右位置，ID为最长匹配的开始位置 有点类似manacher的思想 for(int i=1;i<l;i++) { if(i<=mx) p[i]=min(mx-i,p[i-id]-1); //这个有点像manacher的样子 mx为当前我匹配到的字符串的最右位置 //如果当前i在这个范围内 那他的数值和之前的值有关联 else p[i]=0; while (s[p[i]]==s[i+p[i]]) p[i]++; p[i]=min(l-i,p[i]+1);//这里特判一下 超过串的长度不用匹配 if(i+p[i]-1>mx) id=i,mx=i+p[i]-1; //每次更新一下mx和id ans+=p[i]; } } int main() { int T; scanf("%d",&T); while (T--) { scanf("%s",s); ans=0; solve(); printf("%lld\n",ans); } }