题目分析:详细分析见http://972169909-qq-com.iteye.com/blog/1114968
求:字符串的子串数+最大前后匹配长度
注意:这里的next[i]表示前i个字符所组成的字符串的最大前后缀匹配长度
代码:
#include<iostream> #include<cstdio> #include<cstring> using namespace std; char s[200100]; int next[200100]; int len; void GetNext() { int j=0,k=-1; next[0]=-1; while(j<len) { if(k==-1||s[j]==s[k]) { j++,k++; next[j]=k; } else { k=next[k]; } } } int main() { int ca; scanf("%d",&ca); while(ca--) { scanf("%d",&len); scanf("%s",s); GetNext(); int ans=next[len]+len; for(int i=0;i<len;i++) if(next[i]>0&&next[i]+1!=next[i+1]) ans+=next[i]; printf("%d\n",ans%10007); } system("pause"); return 0; }