双重遍历,暴力求解
'abcaba' // 主串
'abx' // 子串
// 子串与主串对比的过程
// 第一步
// a b c a b a
// a b x 子串x与主串c不相同,将子串下标置为0,主串回到对比之初位置 + 1
// 第二步
// a b c a b a
// a 子串a与主串b不相同,将子串下标置为0,主串回到对比之初位置 + 1
// 第三步
// a b c a b a
// a 子串a与主串c不相同,将子串下标置为0,主串回到对比之初位置 + 1
// 四
// a b c a b a
// a b x 子串x与主串a不相同,将子串下标置为0,主串回到对比之初位置 + 1
// ...主串与子串对比过程中或许有许多部分匹配的情况,而朴素法在双重遍历的时候形成了许多重复的对比,kmp 算法,根据子串的的前后缀相似度,来确定对应对应下标的在对比不匹配的时候应该回溯到的值.
// 主串 "abcaba"
// 子串 "abx"
// 获取子串代表前后缀相似程度的nextArr [-1, 0, 0]
// 第一步
// a b c a b a
// a b x
// 第二步
// a b c a b a
// a b x
// 第三步
// a b c a b a
// a b x
// 第四步
// a b c a b a
// a b x当子串遍历的过程中,需要回溯的时候,当前遍历到的值与将要回溯到的值相同时,再次遍历将毫无意义,所以在获取 nextArr 的时候,可以判断回溯值与当前值是否相等,如果相等,则使用将要回溯值的回溯值作为回溯值