KMP算法原理
KMP算法主要是一种用于字符串匹配的算法，在进行字符串匹配时，当出现字符串不匹配的情况时，可以利用之前已经匹配过的信息避免从头开始匹配。
KMP算法里的next数组表示前缀表，前缀表是在发现模式串与主串不匹配的时候，模式串应该从哪里开始重新匹配。如果使用暴力分配的话，就需要从头开始匹配。
前缀表：记录下标i之前的字符串有多大相同的前缀后缀。
前缀：不包含最后一个字符的所有以第一个字符开始的连续子串
后缀：不包含第一个字符的所有以最后一个字符结尾的连续子串
例如：
a——最长相等前后缀为0，没有前后缀
aa——最长相等前后缀为1，即开始a=结尾a
aab——最长相等前后缀为0
aaba——最长相等前后缀为1，即开始a=结尾a
aabaa——最长相等前后缀为2，即开始aa=结尾aa
28.找出一个字符串中的第一个匹配项的下标
28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）
使用前缀表进行匹配的两种方式
前缀表统一减一后的next数组
步骤：
1.初始化，定义两个指针，i指向后缀末尾，j指向前缀末尾位置
对next数组初始化的代码如下：
int j = -1;
next[0] = j;
因为这里要对next数组实现统一减一的操作，所以j初始化为-1，
next[i]表示最长相等前后缀之前的长度，所以用初始化为j。
2.处理前后缀不相同的情况
用s[i]和s[j+1]进行对比，如果不同，就要对j进行回退操作
3.处理前后缀相同的情况
如果s[i]和s[j+1]相同，那个就把j赋给next[i]，因为next[i]就是记录前后缀的长度。
4.得到next数组以后，就可以用它来做匹配了
class Solution {
public:
void getNext(int* next, const string& s) {
int j = -1;
next[0] = j;
forclass Solution {
public:
void getNext(int* next, const string& s) {
int j = -1;
next[0] = j;
for(int i = 1; i < s.size(); i++) { // 注意i从1开始
while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
j = next[j]; // 向前回退
}
if (s[i] == s[j + 1]) { // 找到相同的前后缀
j++;
}
next[i] = j; // 将j（前缀的长度）赋给next[i]
}
}
int strStr(string haystack, string needle) {
if (needle.size() == 0) {
return 0;
}
vector<int> next(needle.size());
getNext(&next[0], needle);
int j = -1; // // 因为next数组里记录的起始位置为-1
for (int i = 0; i < haystack.size(); i++) { // 注意i就从0开始
while(j >= 0 && haystack[i] != needle[j + 1]) { // 不匹配
j = next[j]; // j 寻找之前匹配的位置
}
if (haystack[i] == needle[j + 1]) { // 匹配，j和i同时向后移动
j++; // i的增加在for循环里
}
if (j == (needle.size() - 1) ) { // 文本串s里出现了模式串t
return (i - needle.size() + 1);
}
}
return -1;
}
};
(int i = 1; i < s.size(); i++) { // 注意i从1开始
while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
j = next[j]; // 向前回退
}
if (s[i] == s[j + 1]) { // 找到相同的前后缀
j++;
}
next[i] = j; // 将j（前缀的长度）赋给next[i]
}
}
int strStr(string haystack, string needle) {
if (needle.size() == 0) {
return 0;
}
vector<int> next(needle.size());
getNext(&next[0], needle);
int j = -1; // // 因为next数组里记录的起始位置为-1
for (int i = 0; i < haystack.size(); i++) { // 注意i就从0开始
while(j >= 0 && haystack[i] != needle[j + 1]) { // 不匹配
j = next[j]; // j 寻找之前匹配的位置
}
if (haystack[i] == needle[j + 1]) { // 匹配，j和i同时向后移动
j++; // i的增加在for循环里
}
if (j == (needle.size() - 1) ) { // 文本串s里出现了模式串t
return (i - needle.size() + 1);
}
}
return -1;
}
};
459.重复的子字符串
题目：给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
步骤：
步骤一：因为 这是相等的前缀和后缀，t[0] 与 k[0]相同， t[1] 与 k[1]相同，所以 s[0] 一定和 s[2]相同，s[1] 一定和 s[3]相同，即：，s[0]s[1]与s[2]s[3]相同 。
步骤二： 因为在同一个字符串位置，所以 t[2] 与 k[0]相同，t[3] 与 k[1]相同。
步骤三： 因为 这是相等的前缀和后缀，t[2] 与 k[2]相同 ，t[3]与k[3] 相同，所以，s[2]一定和s[4]相同，s[3]一定和s[5]相同，即：s[2]s[3] 与 s[4]s[5]相同。
步骤四：循环往复。
所以字符串s，s[0]s[1]与s[2]s[3]相同， s[2]s[3] 与 s[4]s[5]相同，s[4]s[5] 与 s[6]s[7] 相同。
正是因为 最长相等前后缀的规则，当一个字符串由重复子串组成的，最长相等前后缀不包含的子串就是最小重复子串。
class Solution {
public:
void getNext (int* next, const string& s){
next[0] = -1;
int j = -1;
for(int i = 1;i < s.size(); i++){
while(j >= 0 && s[i] != s[j + 1]) {
j = next[j];
}
if(s[i] == s[j + 1]) {
j++;
}
next[i] = j;
}
}
bool repeatedSubstringPattern (string s) {
if (s.size() == 0) {
return false;
}
int next[s.size()];
getNext(next, s);
int len = s.size();
if (next[len - 1] != -1 && len % (len - (next[len - 1] + 1)) == 0) {
return true;
}
return false;
}
};
