HDU 1711（KMP）字符串匹配


     

链接  HDU 1711 Number Sequence

KMP 算法

      我以自己理解写的，写的不对，不明白的地方海王子出来，一起共同学习；

字符串匹配 就是KMP，一般思想，用一个for循环找开头   如果开头一样进入第二个for循环；这样统计  直观 容易理解。但是时间复杂度比较长。所以就有KMP  这个算法了

   KMP 大体思想因为在上一个方法之中，有的字符重复比较了，使得找到目标字符窜效率比较低，


比如   ：目标串为：   ① a b a b c 

              在                 ② a b a a b a b c d a b c d b c  这个字符窜中找到上述目标串；

如用  i，j  来表示①，②两个字符串的下标，假设下标从一开始；

i=1,j=1    a=a;

i=2,j=2    b=b;

i=3,j=3    a=a;

i=4;j=4    b!=a;  此时如果只将①字符串右移动一位，虽然可以；但是，假如你移动两位看看怎么样？

           a b a b c 

     a b a a b a b c d a b c d b c 

是不是觉得移动2格对得非常整齐？

那么为什么移动两个？

第3个a与第一个a正好重复！所以我们知道重复单元就知道移动多少。需要一个数组记录当两个字符不相等，i 应该指向哪个！记录重复单元的值，叫做部分匹配值！不懂可以百度部分匹配值！以上就是KMP 核心思想

下面贴一个代码！！两种写法！//屏蔽是另一种写法

[cpp] view plain copy
  1. #include<iostream>  
  2. #include<stdio.h>  
  3. #include<string.h>  
  4. #include<algorithm>  
  5.   
  6. using namespace std;  
  7.   
  8. int N[1000005],M[10005],a[10005],n,m;  
  9. void set_a()  
  10. {  
  11.     int i,j;  
  12.     a[1]=0;  
  13.     j=1;  
  14.     for(i=2; i<=m; i++)  
  15.     {  
  16.         if(M[j]==M[i])  
  17.         {  
  18.             a[i]=j;  
  19.             j++;  
  20.         }  
  21.         else if(M[j]!=M[i]&&M[i]==M[1])  
  22.         {  
  23.             a[i]=1;  
  24.             j=2;  
  25.         }  
  26.         else  
  27.         {  
  28.             a[i]=0;  
  29.             j=1;  
  30.         }  
  31.     }  
  32. //    for(i=1; i<=m; i++)  
  33. //        printf("%d ",a[i]);  
  34. //    printf(" ");  
  35. }  
  36. int kmp()  
  37. {  
  38.     int i=1,j=1,k;  
  39.     set_a();  
  40.     while(i<=n)  
  41.     {  
  42.         if(j==1&&N[i]!=M[j]) i++;  
  43.         if(N[i]==M[j])  
  44.         {  
  45.             i++;  
  46.             j++;  
  47.         }  
  48.         else j=a[j-1]+1;  
  49.         if(j==m+1) return i-m;  
  50.     }  
  51.     return -1;  
  52. }  
  53. int main()  
  54. {  
  55.     int t;  
  56.     scanf("%d",&t);  
  57.     while(t--)  
  58.     {  
  59.         //int b; scanf("%d",&b);  
  60.         int i;  
  61.         scanf("%d%d",&n,&m);  
  62.         memset(a,0,sizeof(a));  
  63.         for(i=1; i<=n; i++)  
  64.             scanf("%d",&N[i]);  
  65.         for(i=1; i<=m; i++)  
  66.             scanf("%d",&M[i]);  
  67.         printf("%d ",kmp());  
  68.     }  
  69.     return 0;  
  70. }  
  71.   
  72. ///**********************KMP****************************/  
  73. //  
  74. //#include<stdio.h>  
  75. //#include<string.h>  
  76. //using namespace std;  
  77. //int lena,lenb;  
  78. //int a[1000005],b[10005];  
  79. //int next[200000];  
  80. //void set_naxt()//子串的next数组  
  81. //{  
  82. //    int i=0,j=-1;  
  83. //    next[0]=-1;  
  84. //    while(i<lenb)  
  85. //    {  
  86. //        if(j==-1||b[i]==b[j])  
  87. //        {  
  88. //            i++;  
  89. //            j++;  
  90. //            next[i]=j;  
  91. //        }  
  92. //        else  
  93. //            j=next[j];  
  94. //    }  
  95. //    // printf(">>%d ",next[lenb-1]);  
  96. //    for(i=1; i<=lenb; i++)  
  97. //        printf("%d ",next[i]);  
  98. //    printf(" ");  
  99. //}  
  100. //  
  101. //int kmp()  
  102. //{  
  103. //    int i=0,j=0;  
  104. //    set_naxt();  
  105. //    while(i<lena)  
  106. //    {  
  107. //        if(j==-1||a[i]==b[j])  
  108. //        {  
  109. //            i++;  
  110. //            j++;  
  111. //        }  
  112. //        else  
  113. //            j=next[j];  
  114. //        if(j==lenb)  
  115. //            return i-j+1;  
  116. //    }  
  117. //    return -1;  
  118. //}  
  119. //int main()  
  120. //{  
  121. //    int i,t;  
  122. //    scanf("%d",&t);  
  123. //    while(t--)  
  124. //    {  
  125. //        memset(next,0,sizeof(next));  
  126. //        scanf("%d%d",&lena,&lenb);  
  127. //        for(i=0; i<lena; i++)  
  128. //            scanf("%d",&a[i]);  
  129. //        for(i=0; i<lenb; i++)  
  130. //            scanf("%d",&b[i]);  
  131. //        printf("%d ",kmp());  
  132. //    }  
  133. //}  



【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/coded-ream/p/7208017.html