Sample test(s)
input
ABACABA
output
31 43 27 1
input
AAA
output
31 32 2
3 1
/* 大致题意；给一个字符串，，按长度输出和后缀完全匹配的的前缀的长度，及该前缀在整个串中出现的次数。 解法： 这题考察的是对kmp next数组的理解*/#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#include <string>#include <queue>#include <map>#include <stack>#include <set>#include <cmath>#include <vector>#include<cstdlib>#define INF 0x3f#define eps 1e-6#pragma comment (linker,"/STACK:102400000,102400000")using namespace std;#define maxn 100005int next_[maxn];char str[maxn];int ant[maxn];//记录前缀出现的次数int len;int n;void get_next(){int i=0;int j=-1;next_[i]=j;while(i<len){if(j==-1 || str[i]==str[j]){++i;++j;next_[i]=j;}elsej=next_[j];}}void KMP(){int i=0;int j=0;memset(ant,0,sizeof(ant));while(i<len){if(j==-1 || str[i]==str[j]){i++;j++;ant[j]++;}elsej=next_[j];}for(int i=len;i>=0;i–) //大前缀包含小前缀,统计每个前缀出现的个数if(next_[i]!=-1)ant[next_[i] ]+=ant[i];}struct node_{int a;int b;}node[maxn];int main(){while(~scanf("%s",str)){len=strlen(str);get_next();KMP();int tt=len;int ans=0;while(tt){node[ans].a=tt,node[ans].b=ant[tt];tt=next_[tt];ans++;}printf("%d\n",ans);for(int i=ans-1;i>=0;i–){printf("%d %d\n",node[i].a,node[i].b);}}return 0;}
要知道，当你一直在担心错过了什么的时候，
