KMP算法详解

KMP算法常用于在一个串中查找是否出现过另一个串或重复的字符串
核心思想是建立前缀表,前缀表里，统计了各个位置为终点字符串的最长相同前后缀的长度。
最长相同前后缀和重复子串有着千丝万缕的关系
前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串；
后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。
在由重复子串组成的字符串中，最长相等前后缀不包含的子串就是最小重复子串，这里那字符串s：abababab 来举例，ab就是最小重复单位，如图所示：

下面给出next前缀表的实现方式

void getNext (int* next, const string& s){
        next[0] = 0;
        int j = 0;
        for(int i = 1;i < s.size(); i++){
            while(j > 0 && s[i] != s[j]) {
                j = next[j - 1];
            }
            if(s[i] == s[j]) {
                j++;
            }
            next[i] = j;
        }

接下来用C++给出整体实现方式

class Solution {
public:
    void getNext (int* next, const string& s){
        next[0] = 0;
        int j = 0;
        for(int i = 1;i < s.size(); i++){
            while(j > 0 && s[i] != s[j]) {
                j = next[j - 1];
            }
            if(s[i] == s[j]) {
                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] != 0 && len % (len - (next[len - 1] )) == 0) {
            return true;
        }
        return false;
    }
};