KMP,精妙,前后看了3次,到现在终于弄懂了,网上的各种模版很杂,错的也不少,自己写了个。。。
最妙的是next数组的运用,PKU上不少题是不用kmp()函数而巧妙运用next[]数组的。。。
getnext()实际也是一个自身的KMP匹配,怎一个妙字了得~ 广为流传的求法实在是精练,一字不改地照搬了~~
1
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include<stdio.h>
2
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include<string.h>
3
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
4
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int next[255];
5
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
char m[255],s[255];
6
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int cnt,res[255];
7
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
8
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void getnext()
9
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
![](http://www.cppblog.com/Images/dot.gif)
{
10
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int i,j;
11
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
i=0;j=-1;
12
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
next[0]=-1;
13
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
while(s[i])
14
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
![](http://www.cppblog.com/Images/dot.gif)
{
15
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(j==-1||s[i]==s[j])
16
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
next[++i]=++j;
17
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
else
18
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
j=next[j];
19
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif)
}
20
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockEnd.gif)
}
21
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
22
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void kmp()
23
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
![](http://www.cppblog.com/Images/dot.gif)
{
24
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int i,j,len1,len2;
25
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
i=0;j=0;
26
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
len1=strlen(m);
27
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
len2=strlen(s);
28
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
while(i<len1)
29
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
![](http://www.cppblog.com/Images/dot.gif)
{
30
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
while(j!=len2&&m[i]==s[j])//找到当前第一个失配字符
31
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
![](http://www.cppblog.com/Images/dot.gif)
{
32
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
i++;
33
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
j++;
34
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif)
}
35
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(j==0)//第一个字符失配
36
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
i++;
37
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
else if(j==len2)//找到一个匹配串
38
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
![](http://www.cppblog.com/Images/dot.gif)
{
39
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
res[cnt++]=i-j;
40
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
j=next[j];
41
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif)
}
42
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
else//回朔
43
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
j=next[j];
44
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif)
}
45
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockEnd.gif)
}
46
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
47
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
48
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
![](http://www.cppblog.com/Images/dot.gif)
{
49
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
freopen("in.txt","r",stdin);
50
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
scanf("%s%s",m,s);
51
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
// m[]="aabbbabaabbaaabbaabbaabbaabbaabbaa",s[]="aabbaabb";
52
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
cnt=0;
53
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
getnext();
54
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
kmp();
55
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return 0;
56
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockEnd.gif)
}
这两天做了好多KMP:PKU3080,PKU3461,PKU2406,PKU2752
还有恶心的3450,WA到现在了:-( 。。。