Code666 (代码贴、代码片段)

[C++] kmp →→→→→进入此内容的聊天室

来自 , 2020-03-25, 写在 C++, 查看 127 次.
URL http://www.code666.cn/view/9d7311ba
  1. /*
  2.     2016年4月28日10:27:36
  3.     kmp
  4.     注意重复的也算
  5.     p：AZA
  6.     t：AZAZAZA
  7.  
  8.     ans = 3;
  9. */
  10. #include<stdio.h>
  11. #include<string.h>
  12.  
  13. const int maxn = 1e6 + 5;
  14.  
  15. char p[10005];
  16. int next[10005];
  17. char t[maxn];
  18.  
  19. void makenext()
  20. {
  21.     int m = strlen(p);
  22.     next[0] = 0;
  23.     for(int q = 1,k = 0;q < m;q++)
  24.     {
  25.         while(k > 0 && p[q] != p[k])
  26.             k = next[k-1];          //跳到上一个前缀
  27.         if(p[q] == p[k])
  28.             k++;
  29.         next[q] = k;
  30.     }
  31. }
  32. int kmp()
  33. {
  34.     int ans = 0;
  35.     int m = strlen(p);
  36.     int n = strlen(t);
  37.     for(int i = 0,q = 0;i < n;i++)
  38.     {
  39.         while(q > 0 && p[q] != t[i])
  40.             q = next[q-1];
  41.         if(p[q] == t[i])
  42.             q++;
  43.         if(q == m)
  44.         {
  45.             ans++;
  46.             q = next[q-1];  //如果重复的不算的话，q = 0;和上面的k = next[k-1];比较看一下
  47.         }
  48.     }
  49.     return ans;
  50. }
  51. int main()
  52. {
  53.     int T;
  54.     scanf("%d",&T);
  55.     while(T--)
  56.     {
  57.         scanf("%s",p);
  58.         scanf("%s",t);
  59.         makenext();
  60.         printf("%d\n",kmp());
  61.     }
  62.     return 0;
  63. }
  64. /*
  65. 3
  66. BAPC
  67. BAPC
  68. AZA
  69. AZAZAZA
  70. VERDI
  71. AVERDXIVYERDIAN
  72.  
  73. 1
  74. 3
  75. 0
  76. */
  77.  

回复 "kmp"

这儿你可以回复上面这条便签

captcha

贴代码片段 - Code666