hdu 1686(Oulipo) KMP基础题 / hdu 2087（剪花布条）KMP基本运用

r囧r小猫 2021-12-11 11:32 200阅读 0赞

题目太长自己叙述吧！

原题链接地址：[http://acm.hdu.edu.cn/showproblem.php?pid=1686][http_acm.hdu.edu.cn_showproblem.php_pid_1686]

输入：t代表测试实例

第一行：模式串

第二行：匹配串

问模式串在匹配串中出现的次数。

BAPC

AZA

AZAZAZA

VERDI

AVERDXIVYERDIAN

上面的三个实例的输出分别为：1 3 0

KMP算法看了有半天了吧！很朦胧啊！就霸王硬上弓了，套着模板A了这一题！

1 #include<iostream>
     2 #include<cstring>
     3 #include<cstdio>
     4 using namespace std;
     5 #define N 1000006
     6 #define M 10004
     7 char a[M];
     8 char b[N];
     9 int next[M];
    10 int n,m;
    11 void Get_next()
    12 {
    13     int i=0,j=-1;
    14     next[0]=-1;
    15     while(i<m)
    16     {
    17         if(j==-1||a[i]==a[j])
    18         {
    19             i++;
    20             j++;
    21             next[i]=j;
    22         }
    23         else
    24             j=next[j];
    25     }
    26 }
    27 int KMP()
    28 {
    29     int i=0,j=0;
    30     int ans=0;
    31     Get_next();
    32     while(i<n&&j<m)
    33     {
    34       if(j==-1||b[i]==a[j])
    35       {
    36           i++;
    37           j++;
    38       }
    39       else
    40           j=next[j];
    41       if(j==m)
    42         ans++,j=next[j];
    43     }
    44       return ans;
    45 }
    46 int main()
    47 {
    48     int t;
    49     cin>>t;
    50     while(t--)
    51     {
    52         memset(next,-1,sizeof(next));
    53         cin>>a;
    54         m=strlen(a);
    55         cin>>b;
    56         n=strlen(b);
    57         cout<<KMP()<<endl;
    58     }
    59     return 0;
    60 }
    61

hdu 2087 （剪花布条）KMP的基本运用

唯一需要注意的就是当模式串查找到后，j要回到0;

1 #include<iostream>
     2 #include<cstring>
     3 #include<cstdio>
     4 using namespace std;
     5 #define N 1005
     6 char str[N],s[N];
     7 int next[N];
     8 int num;
     9 void get_next()
    10 {
    11 
    12     int i=0,j=-1;
    13     next[0]=-1;
    14     int len=strlen(s);
    15     while(i<len)
    16     {
    17 
    18         if(j==-1||s[i]==s[j])
    19         {
    20             i++;
    21             j++;
    22             next[i]=j;
    23         }
    24         else
    25             j=next[j];
    26     }
    27 }
    28 void KMP()
    29 {
    30 
    31     int i=0,j=0;
    32     int len=strlen(str);
    33     int len2=strlen(s);
    34     while(i<len)
    35     {
    36         if(j==len2)
    37         {
    38             num++;
    39             j=0;
    40         }
    41         if(j==-1||str[i]==s[j])
    42         {
    43             i++;
    44             j++;
    45 
    46         }
    47         else
    48             j=next[j];
    49 
    50     }
    51     if(j==len2)
    52         num++;
    53 }
    54 int main()
    55 {
    56 
    57     while(scanf("%s",str)!=EOF)
    58     {
    59 
    60         if(str[0]=='#')  break;
    61         scanf("%s",s);
    62         get_next();
    63         num=0;
    64         KMP();
    65         printf("%d\n",num);
    66 
    67 
    68     }
    69     return 0;
    70 }

转载于:https://www.cnblogs.com/heat-man/archive/2013/04/26/3044505.html

[http_acm.hdu.edu.cn_showproblem.php_pid_1686]: http://acm.hdu.edu.cn/showproblem.php?pid=1686