SOURCE

/**
 * 方法一：查找字符串的next数组（前缀表-1）
 */ 
function findNext(s) {
    const len = s.length, next = Array(len).fill(-1)
    let j = -1
    next[0] = -1
    for(let i = 1; i < len; i++) {
        while(j >= 0 && s[j+1] !== s[i]) {
            // j = next[j]
            j--
        }
        if(s[j+1] === s[i]) j++
        next[i] = j
    }
    return next
}

// console.log(findNext('aaba'))

// 借助next数组来实现
function indexof(s, t) {
    const arrS = Array.from(s), arrT = Array.from(t)
    let j = -1, next = []
    next = findNext(t)

    for(let i = 0; i < s.length; i++) {
        while(j>=0 && s[i] !== t[j+1]) {
            j = next[j]
        }
        if(s[i] === t[j+1]) j++
        if(j === t.length -1) {
            return i-t.length + 1
        }
    }
    return -1
}

// console.log(indexof('aabaafa', 'aaf'))

/**
 * 方法二：下面写法直接使用前缀表来实现
 */ 
// 查找字符串的前缀表（next[i] 表示0-i的最长相同前后缀）
function findNext2(s) {
    const len = s.length, next = Array(len)
    let j = 0
    next[0] = 0
    for(let i = 1; i < len; i++) {
        while(j > 0 && s[j] !== s[i]) {
            j = next[j-1]
            // j--
        }
        if(s[j] === s[i]) j++
        next[i] = j
    }
    return next
}
// console.log(findNext2('asdfasdfasdf'))

function indexof2(s, t) {
    const arrS = Array.from(s), arrT = Array.from(t)
    let j = 0, next = []
    next = findNext2(t)

    for(let i = 0; i < s.length; i++) {
        while(j>0 && s[i] !== t[j]) {
            j = next[j-1]
        }
        if(s[i] === t[j]) j++
        if(j === t.length) {
            return i-t.length + 1
        }
    }
    return -1
}
// console.log(indexof2('aabaafa', 'aaf'))


/**
 * 判断字符串是否由重复的子串组成
 * eg: 'adad' 返回true, 'ada' 返回false
*/
function subStr(s) {
    const len = s.length
    let next = findNext2(s)
    if(next[len-1] !== 0 && len %  (len - next[len-1]) === 0) return true
    return false
}

console.log(subStr('asdfasdfasdf'))