459. 重复的子字符串[kmp]

459. 重复的子字符串

const getNext = (s: string) => {
    let matchLen = 0;
    const next:number[] = [];
    let i = 0;
    next[i] = matchLen;
    for(i=1;i<s.length;i++) {
        while(matchLen>0 && s[i]!==s[matchLen]){
            matchLen = next[matchLen-1];
        }
        if(s[i]===s[matchLen]) {
            matchLen+=1;
        }
        next[i] = matchLen;
    }
    return next;
};

function repeatedSubstringPattern(s: string): boolean {
    const next = getNext(s);
    const len =s.length;
    if(next[len-1]!=0 && len % (len - next[len-1]) === 0){
        return true;
    }
    return false;
};

console.log('repeatedSubstringPattern', repeatedSubstringPattern('ababab'));