Codeforces Round #246 (Div. 2) D. Prefixes and Suffixes(后缀数组orKMP)(二)
],ct,n;
void getf(char *p)
{
int i,j;
f[0]=f[1]=0;
for(i=1;i
0;j--)//为什么可以这样做呢。终点不同的串一定是不同的串。kmp保证了终点不同。 if(f[j])//f[j]表示下个比较的位置。说明前f[j]-1一定是相同的。 cnt[f[j]-1]+=cnt[j-1]; while(t)//前缀匹配后缀 { ansp[ct]=t; ansn[ct++]=cnt[t-1]; t=f[t]; } printf("%d\n",ct); for(i=ct-1;i>
=0;i--) printf("%d %d\n",ansp[i],ansn[i]); } int main() { while(~scanf("%s",txt)) { n=strlen(txt); memset(cnt,0,sizeof cnt); getf(txt); KMP(); } }