28. 找出字符串中第一個(gè)匹配項(xiàng)的下標(biāo)
題目：
給你兩個(gè)字符串 haystack 和 needle 霞势，請(qǐng)你在 haystack 字符串中找出 needle 字符串的第一個(gè)匹配項(xiàng)的下標(biāo)（下標(biāo)從 0 開(kāi)始）烹植。如果 needle 不是 haystack 的一部分，則返回 -1 愕贡。
示例：
輸入：haystack = "sadbutsad", needle = "sad"
輸出：0
解釋?zhuān)?sad" 在下標(biāo) 0 和 6 處匹配草雕。
第一個(gè)匹配項(xiàng)的下標(biāo)是 0 ，所以返回 0 固以。
解題思路
利用KMP算法來(lái)實(shí)現(xiàn)墩虹，分為兩步：
- 求next數(shù)組：
- 初始化：定義兩個(gè)指針，j 指針指向前綴末尾憨琳，i 指針指向后綴末尾诫钓。
- 前后綴不相同：前后元素進(jìn)行對(duì)比，如果不相同就開(kāi)始向前回退篙螟。
- 前后綴相同：前后元素對(duì)比菌湃，如果相同就繼續(xù)后移 j。
- 使用next數(shù)組進(jìn)行匹配：
從起始值開(kāi)始匹配遍略，當(dāng)遇到不相等的情況就回退next數(shù)組的位置惧所，相等就開(kāi)始計(jì)數(shù)，直到找到绪杏。
const getNext = (needle) => {
let next = [];
let j = 0;
next.push(j);
for (let i = 1; i < needle.length; i++) {
while (j > 0 && needle[i] !== needle[j]) {
j = next[j - 1];
}
if (needle[i] === needle[j]) {
j++;
}
next.push(j);
}
return next;
}
var strStr = function (haystack, needle) {
let next = getNext(needle);
let j = 0;
for (let i = 0; i < haystack.length; i++) {
while (j > 0 && haystack[i] !== needle[j]) {
j = next[j - 1];
}
if (haystack[i] === needle[j]) {
j++;
}
if (j === needle.length) {
return i - needle.length + 1;
}
}
return -1;
};
459. 重復(fù)的子字符串
題目：
給定一個(gè)非空的字符串 s 下愈，檢查是否可以通過(guò)由它的一個(gè)子串重復(fù)多次構(gòu)成。
示例：
輸入: s = "abab"
輸出: true
解釋: 可由子串 "ab" 重復(fù)兩次構(gòu)成蕾久。
解題思路：
1. 移動(dòng)匹配
把兩段拼起來(lái)势似，如果在中間能找到其中的一段就說(shuō)明存在重復(fù)子串。
var repeatedSubstringPattern = function (s) {
return (s + s).slice(1, s.length * 2 - 1).indexOf(s) === -1 ? false : true;
};
2. KMP算法
當(dāng)一個(gè)字符串由重復(fù)子串組成的僧著，最長(zhǎng)相等前后綴不包含的子串就是最小重復(fù)子串叫编。要注意這里next數(shù)組不能是0，這種情況是和整個(gè)串相等霹抛，不符合要求搓逾。
const getNext = (needle) => {
let next = [];
let j = 0;
next.push(j);
for (let i = 1; i < needle.length; i++) {
while (j > 0 && needle[i] !== needle[j]) {
j = next[j - 1];
}
if (needle[i] === needle[j]) {
j++;
}
next.push(j);
}
return next;
}
var repeatedSubstringPattern = function (s) {
let next = getNext(s);
console.log(next)
if (next[next.length - 1] !== 0 && s.length % (s.length - next[next.length - 1]) === 0) {
return true;
}
return false
};
