KMP，精妙，前后看了3次，到現(xiàn)在終于弄懂了，網(wǎng)上的各種模版很雜，錯(cuò)的也不少，自己寫了個(gè)。。。
最妙的是next數(shù)組的運(yùn)用，PKU上不少題是不用kmp()函數(shù)而巧妙運(yùn)用next[]數(shù)組的。。。
getnext()實(shí)際也是一個(gè)自身的KMP匹配，怎一個(gè)妙字了得~ 廣為流傳的求法實(shí)在是精練，一字不改地照搬了~~
1
#include<stdio.h>
2
#include<string.h>
3
4
int next[255];
5
char m[255],s[255];
6
int cnt,res[255];
7
8
void getnext()
9
{
10
int i,j;
11
i=0;j=-1;
12
next[0]=-1;
13
while(s[i])
14
{
15
if(j==-1||s[i]==s[j])
16
next[++i]=++j;
17
else
18
j=next[j];
19
}
20
}
21
22
void kmp()
23
{
24
int i,j,len1,len2;
25
i=0;j=0;
26
len1=strlen(m);
27
len2=strlen(s);
28
while(i<len1)
29
{
30
while(j!=len2&&m[i]==s[j])//找到當(dāng)前第一個(gè)失配字符
31
{
32
i++;
33
j++;
34
}
35
if(j==0)//第一個(gè)字符失配
36
i++;
37
else if(j==len2)//找到一個(gè)匹配串
38
{
39
res[cnt++]=i-j;
40
j=next[j];
41
}
42
else//回朔
43
j=next[j];
44
}
45
}
46
47
int main()
48
{
49
freopen("in.txt","r",stdin);
50
scanf("%s%s",m,s);
51
// m[]="aabbbabaabbaaabbaabbaabbaabbaabbaa",s[]="aabbaabb";
52
cnt=0;
53
getnext();
54
kmp();
55
return 0;
56
}
還有惡心的3450，WA到現(xiàn)在了:-( 。。。