leetcode28找出字符串第一个匹配值的下标KMP算法

KMP 算法——快速的从主串中找到模式串

当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。

KMP 算法 比较指针不回溯，仅仅是后移模式串。

每次不匹配的时候，找之前已匹配部分中，模式串的最长公共前后缀。

前缀与后缀相同，所以T里面与P的后缀a匹配的那个a一定也与P中的前缀a匹配，所以直接从前缀后面的b开始匹配就行了

也就是碰到某个不匹配的时候，我这个模式串要从最长前缀后滑动到最长后缀的位置（其实就是比较指针 j 从最长前缀移动到最长后缀的位置）。而保存这个位置的数组就是 next 数组。

next数组——前缀表（prefix table）

前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。

next数组既可以就是前缀表，也可以是前缀表统一减一（右移一位，初始位置为-1）。

帮你把KMP算法学个通透！（求next数组代码篇）_哔哩哔哩_bilibili

构造next数组：

定义一个函数getNext来构建next数组，函数参数为指向next数组的指针，和一个字符串。定义一个函数getNext来构建next数组，函数参数为指向next数组的指针，和一个字符串。

int* next 的含义 void getNext(int* next, const string& s);

int* next 是一个指向整型数组的指针。

它表示 next 是一个数组，而不是单个整数。

在函数内部，可以通过 next[i] 访问数组的第 i 个元素。

getNext(&next[0], needle); 的语义

next 是一个整型数组，例如 int next[10];。

&next[0] 是数组 next 的首地址，类型是 int*。

通过 int* next 参数，函数可以访问和修改整个数组。

next数组里存储的是对应位置最长公共前后缀值、当前后缀不相同时j回退到next[j-1]值对应坐标（需要j大于等于1时）。相同时j++更新next。

 

class Solution { public: //求next数组 void getNext(int* next, const string& s){ //初始化 int i = 1;//后缀末尾位、主串所在 int j = 0;//前缀末尾位、最长公共前后缀长度 next[0] = 0; for(int i = 1; i<s.size(); i++){ while(j >= 1 && s[i] != s[j]){ j = next[j-1];//当前后缀不相同，j回退到next[j-1]值对应坐标 } if(s[i] == s[j]){ j++;//前后缀相等最长公共前后缀长度+1、准备比较下一位是否相等 } next[i] = j;//更新next数组值 } } int strStr(string haystack, string needle) { if(needle.size() == 0){ return 0; } vector<int> next(needle.size()); getNext(&next[0], needle); int j = 0; for(int i = 0; i < haystack.size(); i++){ while(j > 0 && haystack[i] != needle[j]){ j = next[j-1]; } if(haystack[i] == needle[j]){ j++; } if(j == needle.size()){ return (i-needle.size()+1); } } return -1; } };