KMP算法

KMP算法讲解：

https://blog.csdn.net/v_july_v/article/details/7041827

next数组讲解：https://www.cnblogs.com/tangzhengyue/p/4315393.html

代码：

 1 int KmpSearch(char* s, char* p)
 2 {
 3     int i = 0;
 4     int j = 0;
 5     int sLen = strlen(s);
 6     int pLen = strlen(p);
 7 
 8     int* next = GetNext(p, next);
 9     while (i < sLen && j < pLen)
10     {
11         //①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++    
12         if (j == -1 || s[i] == p[j])
13         {
14             i++;
15             j++;
16         }
17         else
18         {
19             //②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]    
20             //next[j]即为j所对应的next值      
21             j = next[j];
22         }
23     }
24     return j == pLen? i-j : -1;
25 }

 1 //优化过后的next 数组求法
 2 void GetNext(char* p)
 3 {
 4     int pLen = strlen(p);
 5     int* next = new int[pLen]();
 6     next[0] = -1;
 7     int k = -1;
 8     int j = 0;
 9 
10     // 根据已知的前j位推测第j+1位, 当前为第j+1位
11     while (j < pLen - 1)
12     {
13         //p[k]表示前缀，p[j]表示后缀  
14         if (k == -1 || p[j] == p[k])
15         {
16             //较之前next数组求法，改动在下面4行
17             if (p[j+1] != p[k+1])
18                 next[++j] = ++k;   //之前只有这一行
19             else
20                 //如果p[k+1]==p[j+1]，表明回退后仍然失配（因为p[j+1]失配），所以要继续回退
21                 next[++j] = next[++k];
22         }
23         else
24         {
25             k = next[k];
26         }
27     }
28 }