?????? 統(tǒng)計(jì)前綴后綴相等的個(gè)數(shù)，包括自身，從小到大輸出。可以通過(guò)next[]向前統(tǒng)計(jì)。因?yàn)槊恳粋€(gè)next[i]都指向該串前部字串（p0p1..pk-1）與i之前字串相等(pi-k+1...pi-2pi-1)的最大字串，只要再向前統(tǒng)計(jì)字串的匹配個(gè)數(shù)，即可得到更小的匹配情況。

???? 還有，開(kāi)大的數(shù)組的話，不能子main（）里面開(kāi)，會(huì)stack overflow in main.ext.

???

#include <iostream>
#include <fstream>
#include <string.h>

using namespace std;

int next[400001],a[400001];
char str[400001];

void get_next(char* s)
{
int i=0,j=-1,len=strlen(s);
next[i]=j;
while(i<len)
{
if(j==-1 || s[i]==s[j])
{
i++; j++;
next[i]=j;
}
else
j=next[j];
}
}

int main()
{
int i,j,sum;
freopen("acm.txt","r",stdin);
while( scanf("%s",str)!=EOF )
{
get_next(str);
j=strlen(str);
sum=0;
//向前統(tǒng)計(jì) 要包括自身的長(zhǎng)度
while(j!=0)
{
a[sum++]=j;
j=next[j];
}
for(i=sum-1; i>=0; i--)
{
if(i==sum-1)
printf("%d",a[i]);
else
printf(" %d",a[i]);
}
printf("\n");
}
return 0;
}

?

轉(zhuǎn)載于:https://www.cnblogs.com/Jason-Damon/archive/2012/04/04/2431891.html

總結(jié)

以上是生活随笔為你收集整理的poj2752 字符串子KMP应用的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。