洛谷 P3375 【模板】KMP字符串匹配 || HDU 1686 …

2018-06-17 21:55:33来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

HDU-1686

P3375

kmp介绍:

http://www.matrix67.com/blog/archives/115

http://www.cnblogs.com/SYCstudio/p/7194315.html

http://blog.chinaunix.net/uid-8735300-id-2017161.html(mp&kmp)

http://www-igm.univ-mlv.fr/~lecroq/string/node8.html(mp&kmp,看上去很正确的例程)

http://blog.csdn.net/joylnwang/article/details/6778316

洛谷P3375:

字符串下标从1开始:

 1 #include<cstdio>
 2 #include<cstring>
 3 char s1[1000010],s[1010];
 4 int f[1010];
 5 int n,m;
 6 void getf()
 7 {
 8     int i,j=0;
 9     f[0]=-1;f[1]=0;
10     for(i=2;i<=m;i++)
11     {
12         //j=f[i-1]其实开始的时候j是这个值
13         while(j>=0&&s[j+1]!=s[i])    j=f[j];
14         j++;
15         /*这一步后就是满足s[1..j]==s[i-j+1..i]
16         显然如果找不到任何j那么j应该为0,而-1+1=0,所以f[0]=-1,
17         否则应当为s[1..i-1]的某个相同的前缀后缀且它们之后都为s[i]*/
18         f[i]=j;
19     }
20 }
21 void kmp()
22 {
23     int ans=0,i,j=0;
24     for(i=1;i<=n;i++)
25     {
26         //初始时j为s[1..j]==s[i-1-j+1..i-1]
27         while(j>=0&&s[j+1]!=s1[i])    j=f[j];
28         j++;
29         //此时使得s往后移到了正确的位置
30         /*例如ABABABC/ABC:i=3时j=1,也就是s开头1位跟s1[1..i]对齐
31         又如ABDBA/ABC:i=3时j=0,也就是s开头0位跟s1[1..i]对齐*/
32         if(j==m)
33         {
34             //ans++;
35             printf("%d\n",i-m+1);
36             j=f[j];
37         }
38     }
39     //return ans;
40 }
41 int main()
42 {
43     int i;
44     scanf("%s%s",s1+1,s+1);
45     n=strlen(s1+1);
46     m=strlen(s+1);
47     getf();
48     kmp();
49     for(i=1;i<=m;i++)
50         printf("%d ",f[i]);
51     return 0;
52 }

字符串下标从0开始,加上某个优化后开两个f:

 1 #include<cstdio>
 2 #include<cstring>
 3 int f[1010],f2[1010];
 4 char s1[1000100],s[1010];
 5 int n,m;
 6 void getf()
 7 {
 8     int i=0,j=f[0]=-1;
 9     while(i<m)
10     {
11         while(j>=0&&s[j]!=s[i])    j=f[j];
12         ++i;++j;
13         f[i]=s[i]==s[j]?f[j]:j;
14         f2[i]=j;
15     }
16 }
17 void kmp()
18 {
19     int i=0,j=0;
20     while(i<n)
21     {
22         while(j>=0&&s[j]!=s1[i])    j=f[j];
23         ++i;++j;
24         if(j==m)    printf("%d\n",i-m+1);
25     }
26 }
27 int main()
28 {
29     int i;
30     scanf("%s%s",s1,s);
31     n=strlen(s1);
32     m=strlen(s);
33     getf();
34     kmp();
35     for(i=1;i<=m;i++)
36         printf("%d ",f2[i]);
37     return 0;
38 }

HDU-1686:

程序1的f[i]的含义是能使s[0..p-1]==s[i-p..i-1]的最大的p。字符串下标从0开始。也就是如果当对齐原串下标i的是模板串下标j时发生失配,可以将对齐原串下标i的改为模板串下标f[j]。

程序1(蓝书模板)(f[0]定义为0):

 1 #include<cstdio>
 2 #include<cstring>
 3 int f[10100];
 4 char s1[1000100],s[10100];
 5 void getFail(char *P,int *f)
 6 {
 7     int m=strlen(P);
 8     f[0]=0;f[1]=0;
 9     for(int i=1;i<m;i++)
10     {
11         int j=f[i];
12         while(j&&P[i]!=P[j])    j=f[j];
13         f[i+1]=P[i]==P[j]?j+1:0;
14     }
15 }
16 int find(char *T,char *P,int *f)
17 {
18     int n=strlen(T),m=strlen(P),ans=0;
19     getFail(P,f);
20     int j=0;
21     for(int i=0;i<n;i++)
22     {
23         while(j&&P[j]!=T[i])    j=f[j];
24         if(P[j]==T[i])    j++;
25         if(j==m)    ans++;
26     }
27     return ans;
28 }
29 int main()
30 {
31     int t;
32     scanf("%d",&t);
33     while(t--)
34     {
35         scanf("%s%s",s,s1);
36         printf("%d\n",find(s1,s,f));
37     }
38     return 0;
39 }

程序2(魔改蓝书&某个例程)(f[0]定义为-1,已经加了某个优化):

 1 #include<cstdio>
 2 #include<cstring>
 3 int f2[10100];
 4 char s1[1000100],s[10010];
 5 void getFail(char *P,int *f)
 6 {
 7     int m=strlen(P),j=f[0]=-1,i=0;//i初始值不能为1
 8     while(i<m)
 9     {
10         while(j>=0&&P[i]!=P[j])    j=f[j];
11         ++j;++i;
12         f[i]=P[i]==P[j]?f[j]:j;//改为f[i]=j就是没有优化
13     }
14 }
15 int find(char *T,char *P,int *f)
16 {
17     int n=strlen(T),m=strlen(P),ans=0;
18     getFail(P,f);
19     int i=0,j=0;
20     while(i<n)
21     {
22         while(j>=0&&P[j]!=T[i])    j=f[j];
23         ++i,++j;
24         if(j==m)    ans++;//本来还有一句j=f[j],但这句可以去掉,因为此时j==m,P[j]=='\0',一定不等于T[i],一定执行j=f[j]
25     }
26     return ans;
27 }
28 int main()
29 {
30     int t;
31     scanf("%d",&t);
32     while(t--)
33     {
34         scanf("%s%s",s,s1);
35         printf("%d\n",find(s1,s,f2));
36     }
37     return 0;
38 }

为什么当s[i]!=s[j]时,j=f[j]:

http://blog.csdn.net/qq_30974369/article/details/74276186

http://blog.csdn.net/yutianzuijin/article/details/11954939/

http://blog.csdn.net/wangbaochu/article/details/50687160

(要求从next[i]一段的末尾找到一段k,使得k和(开头的next[i]开头的)一段相同。也就是在next[i]的一段中找出开头和结尾相等的一段。(根据第2、3个博客的图))

 

将各个段从左到右编号为1(灰)、2(紫)、3(红)、4(灰)、5(绿)、6(黑)、7(灰)、8(红)、9(灰)、10(蓝)、11(黑)。

现在的情况是要寻找1-10这大段的最长公共前后缀。用f[n]表示1-n这一段的最长公共前后缀(或其长度),s[n]表示n位置的值。

如果s[5]==s[10],那么显然1-10的公共前后缀可以是f[9]的后面加上一个10。

可以证明这就是1-10的最长公共前后缀:如果不是,也就是f[10]>f[9]+1,也就是f[10]-1>f[9],那么将f[10]删除尾部的s[10],剩下长度为f[10]-1,那么剩下的部分是1-9的公共前后缀,且其长度大于f[9],矛盾。

如果s[5]!=s[10],那么就是要在1-9中找出1-x使得1-x一段是1-9的公共前后缀且s[x+1]==s[10]。

先考虑第一个条件,再去满足第二个:那么也就是要找出1段和9段相同且不等于1-4段。由于1-4段和7-9段是1-9段的公共前后缀,那么1-4段==7-9段,也就是可以在7-9段中找到7段对应1段,在1-4段中找到4段对应9段。可以知道1、4、7、9段都相等。

由于1、4段相等,1、4段也是1-4这一段的公共前后缀。因此可以直接找f[4],结果也就是1-9段的次长公共前后缀。如果还是不行,就找f[f[4]],f[f[f[4]]],...

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:C++ 校园管理系统、高校人员信息管理系统设计

下一篇:P1328 生活大爆炸版石头剪刀布