NO6——KMP

  1 int next[N];
  2 char str1[M],str2[N];
  3 //str1 长，str2 短
  4 //len1,len2,对应str1,str2的长
  5 
  6 void get_next(int len2)
  7 {
  8     int i = 0,j = -1;
  9     next[0] = -1;
 10     while(i<len2)
 11     {
 12         if(j == -1 || str2[i] == str2[j])
 13         {
 14             i++;
 15             j++;
 16             if(str2[i] != str2[j])
 17                 next[i] = j;
 18             else
 19                 next[i] = next[j];
 20         }
 21         else
 22             j = next[j];
 23     }
 24     //计算某字符串的周期，如aaaa是4，abcd是1
 25     /*
 26     int i = 0;j = -1;
 27     next[0] = -1;
 28     while(str2[i])
 29     {
 30         if(j == -1 || str2[i] == str2[j])
 31         {
 32             i++;j++;
 33             next[i] = j;
 34         }
 35         else
 36         j = next[j];
 37     }
 38     len = strlen(str);
 39     i = len-j;
 40     if(len%i==0)
 41     return len/i;
 42     else
 43     return 1;
 44     */
 45 }
 46 
 47 int kmp(int len1,int len2)
 48 {
 49     int i = 0,j = 0;
 50     get_next(len2);
 51     while(i<len1)
 52     {
 53         if(j == -1 || str1[i] == str2[j])
 54         {
 55             i++;
 56             j++
 57         }
 58         else
 59             j = next[j];
 60         /*
 61                 if(j == len2)//计算str2在str1中出现多少次
 62                 {
 63         cnt++;
 64         j= next[j];
 65                 }
 66                 */
 67     }
 68     //return j; //j为匹配的长度
 69     if(j>len2)
 70         return 1;//这里也可以返回i-len2来获得匹配在主串中开始的位置
 71     else
 72         return 0;
 73 }
 74 
 75 //数字KMP
 76 int a[1000005],b[10005];
 77 int next[10005],n,m;
 78 
 79 void getnext()
 80 {
 81     int i = 0,j = -1;
 82     next[0] = -1;
 83     while(i<m)
 84     {
 85         if(j == -1 || b[i] == b[j])
 86         {
 87             i++;
 88             j++;
 89             if(b[i] == b[j])
 90             next[i] = next[j];
 91             else
 92             next[i] = j;
 93         }
 94         else
 95         j = next[j];
 96     }
 97 }
 98 
 99 int kmp()//返回匹配位置
100 {
101     int i = 0,j = 0;
102     while(i<n)
103     {
104         if(a[i] == b[j])
105         {
106             if(j == m-1)
107             return i-j+1;
108             i++;
109             j++;
110         }
111         else
112         {
113             j = next[j];
114             if(j == -1)
115             {
116                 i++;
117                 j = 0;
118             }
119         }
120     }
121     return -1;
122 }