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[],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 }