leetcode 459. Repeated Substring Pattern | KMP

Description
Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.

Example 1:
Input: "abab"

Output: True

Explanation: It's the substring "ab" twice.
Example 2:
Input: "aba"

Output: False
Example 3:
Input: "abcabcabcabc"

Output: True

Explanation: It's the substring "abc" four times. (And the substring "abcabc" twice.)

Solution
discussには多くの巧妙な方法があり、コードが簡潔であればあるほど内蔵関数を利用する傾向があり、本質的には文字列比較を行う.
29 ms CPP simple solution. No KMP.

class Solution {
public:
    bool repeatedSubstringPattern(string str) {
        string nextStr = str;
        int len = str.length();
        if(len < 1) return false;
        for(int i = 1; i <= len / 2; i++){
            if(len % i == 0){
                nextStr = leftShift(str, i);
                if(nextStr == str) return true;
            }
        }
        return false;
    }
    
    string leftShift(string &str, int l){
        string ret = str.substr(l);
        ret += str.substr(0, l);
        return ret;
    }
};

//        ... = =,     i    
class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int n = s.size();
        string head, rear,news;
        for (int i = 1; i < n; ++i) {
            head = s.substr(0, i);
            rear = s.substr(i, s.size());
            news = rear+head;
            if(s==news) return true;
        }
        return false;
    }
};

Easy python solution with explaination
Basic idea:
First char of input string is first char of repeated substringLast char of input string is last char of repeated substringLet S1 = S + S (where S in input string)Remove 1 and last char of S1. Let this be S2If S exists in S2 then return true else falseLet i be index in S2 where S starts then repeated substring length i + 1 and repeated substring S[0: i+1]

def repeatedSubstringPattern(self, str):

        """
        :type str: str
        :rtype: bool
        """
        if not str:
            return False
            
        ss = (str + str)[1:-1]
        return ss.find(str) != -1

C++ O(n) using KMP, 32ms, 8 lines of code with brief explanation.
First, we build the KMP table.
Roughly speaking, dp[i+1] stores the maximum number of characters that the string is repeating itself up to position i.Therefore, if a string repeats a length 5 substring 4 times, then the last entry would be of value 15.To check if the string is repeating itself, we just need the last entry to be non-zero and str.size() to divide (str.size()-last entry).

    bool repeatedSubstringPattern(string str) {
        int i = 1, j = 0, n = str.size();
        vector dp(n+1,0);
        while( i < str.size() ){
            if( str[i] == str[j] ) dp[++i]=++j;
            else if( j == 0 ) i++;
            else j = dp[j];
        }
        return dp[n]&&dp[n]%(n-dp[n])==0;
    }

KMPのπの確立(またはnextの確立)過程について理解するs = "ababaaa"を例にとると、π = [0012311]が得られやすく、このπが最大の接尾辞繰返しビット数であり、kmpの核心思想は自身と自身の繰返し過程を記録することであり、next配列を用いて次のステップがpatternのどの位置にジャンプすべきかを指導する.一般に、next = [-1,π](または-1を0とする)では、nextのi+1番目の要素は、0からiまでのpatternのsubstr、接頭辞および接尾辞の繰り返し要素の個数がnext[i]と解読する.この観点を深く理解すれば、kmpの作業過程を明らかにしやすい.上記のsを例にとります.
π
sを見ると、a->0 by defineab->00「ab」というサブストリング(すなわち0からiまでのpatternのsubstr)は、前接尾辞繰返しaba->001「aba」の先頭の「a」が前接尾辞繰返しababab->0012であり、「ab」は繰返しの前後接尾辞として現れ、要素個数2 aba->00123 aba**とxabaも前後接尾辞繰返しの形式である.繰り返し要素の個数(すなわち、接頭辞または接尾辞の長さ)は3 abaa->001231 abaであり、次はaba b xxであり、接尾辞はxxxaba aであり、等しくない!したがって、このときの接尾辞探索方式はaba xからa x(abマッチング)に変化する、a aもa bの接頭辞形式(接尾辞は...aaであり、最前面はaaのような形式ではない)に合致しないため、a′x′はxと先頭を探すaとのマッチングに再び退化する.頭文字と尾文字のaは同じなので、ここの前接尾辞はすべて「a」なので、ここに1を記入します.ababaaa->依然として先頭と末尾の最大繰返しスタイルは「a」
next
πの前に0を加えるとnext配列になる.nextは指導的意義があり、具体的な生成過程および文字マッチング過程における指導的意義は以下の図(next[next[j]]反復構想の理解に重点を置いた理由)である.
next code

上記のように

.

int i = 1, j = 0;
vector next(n+1,0);
while( i < str.size() ){
    if( str[i] == str[j] ) next[++i]=++j;    //  i+1  i           
    else if( j == 0 ) i++;    // pattern   ,   i++
    else j = next[j];  //    str,   pattern,        
}
next[0] = -1;

別の方法|推奨

int j = -1, i = 0;
next[0] = -1;
while (i < str.size()) {
    if (j == -1 || str[i] == str[j]) next[++i] = ++j;
    else j = next[j];
}

debugは2つの実装方式を撫でて発見し、第1の実装は多くの付与シーンをスキップし(si=sjの場合にのみ付与されるため)、スキップ位置はデフォルトで0であるため、全0に初期化する必要がある.第2の方式は全0初期化を行う必要がなく、付与回数もwhile毎に付与する.
KMP
next配列があれば、patternの中でjがどのようにジャンプすべきかがわかります.patternを別のstrにマッチングするため、next解はpatternがpatternにマッチングするので、下記のコードは論理的にnextを解くことと一致することができます.

int KMP(string &s1,string &s2,vector&next){
    int i=0,j=0,len1=s1.size(),len2=s2.size();
    while(i

Reference

leetcode 459. Repeated Substring Pattern