KMP算法

KMP算法算是我接触的第一个字符串算法，以前不理解，现在稍微理解了，谨以此记。

KMP算法最核心的部分是NEXT数组，也就是模式串匹配的真前缀与真后缀的关系。

对于字符串"abca"的真前缀和真后缀都是a即next数组里的next[4]=1;

next数组next[i]表示的是下表从1-i的真后缀等于真前缀的字符数。

如字符串T”abd“与字符串S”abcdabc“匹配,发现第三个字母d与c不相等，然后找next[2]=0,T串从0也就是a开始与c匹配

T串下标是从0开始，S串是1开始，next数组是S串的真前后缀匹配数；大概就这样；

最核心的是next数组代码；博主手动在网页敲的难免会有瑕疵。

 1 int next[100];
 2 void getnext(string &s)
 3 {
 4     int j=0;//T串的下标指针 
 5     next[1]=0;//s串第一个元素是自己没有真前后缀；
 6     for(int i=2;i<=s.size();i++)
 7     {
 8         while(j&&s[i]!=s[j+1])j=next[j]//同一个串的下标转换
 9         if(s[i]==s[j+1])j++;
10         next[i]=j; 
11      } 
12  } 

第一次用这个网页写好不熟悉啊！

这样KMP算是完整结束了，思想和代码都结束了。

leetcode 28实现 strStr() 函数。

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回  -1 。

 1 class Solution {
 2 public:
 3     int strStr(string haystack, string needle) {
 4         int n=needle.size();
 5         if(!n)return 0;
 6         int next[n+2];
 7         next[1]=0;
 8         int j=0;
 9         for(int i=2;i<=n;i++)
10         {
11             while(j&&needle[i-1]!=needle[j])j=next[j];
12             if(needle[i-1]==needle[j])j++;
13             next[i]=j;
14         }
15         j=0;
16        for(int i=1;i<=haystack.size();i++)
17        {
18          while(j&&haystack[i-1]!=needle[j])j=next[j];
19          if(haystack[i-1]==needle[j])j++;
20          if(j==n)return i-n;
21          
22        }
23     return -1;
24     }
25 };