可恶每天都起的很晚，研究生还是研究死啊
学习计划
1.每天刷3道算法
28找出字符串中第一个匹配项的下标
2.刷面试题
3.构建论文框架
var strStr = function (haystack, needle) {
// 考虑特殊情况字串为空的时候
if (needle.length === 0)
return 0;
// 下面这个方法是用来制造前缀表
const getNext = (needle) => {
// next储存前缀表
let next = [];
// 初始值为-1
let j = -1;
// 把初始值放进数组中
next.push(j);
// 遍历字串
for (let i = 1; i < needle.length; ++i) {
while (j >= 0 && needle[i] !== needle[j + 1])
// 当前后缀不相等的时候
j = next[j];
// 当前后缀相等的时候，加1
if (needle[i] === needle[j + 1])
j++;
next.push(j);
}
// 返回最后next的长度
return next;
}
let next = getNext(needle);
let j = -1;
// 开始遍历 haystack
for (let i = 0; i < haystack.length; ++i) {
// 处理不匹配的情况
while (j >= 0 && haystack[i] !== needle[j + 1])
j = next[j];
// 处理匹配的情况
if (haystack[i] === needle[j + 1])
j++;
// 检查是否找到完整匹配:
if (j === needle.length - 1)
return (i - needle.length + 1);
}
return -1;
};在 KMP（Knuth-Morris-Pratt）字符串匹配算法中，前缀表用于存储“部分匹配值”（Partial Match Table），这些值表示字符串中每个位置的最长相等的真前缀和真后缀的长度。例如：
"ABABC"，前缀表是 [0, 0, 1, 2, 0]。"ABA"）时，最长的相等的真前缀和真后缀是 "A"，其长度为 1。使用前缀表的优点是，在 KMP 算法中匹配失败时，我们可以使用这个表来跳过不必要的比较。
haystack: "abcabcaabcabcabcacab"needle: "abcabcacab"我们的目标是找到 needle 在 haystack 中第一次出现的位置。
特殊情况处理：
needle 非空，我们继续执行。构建前缀表：
getNext(needle) 为 needle 构建前缀表。needle "abcabcacab"，我们得到的前缀表可能类似于 [-1, 0, 0, 1, 2, 3, 4, 5, 0, 1]。假设我们有模式串 needle，构建其前缀表的步骤如下：
初始化：
next，长度与 needle 相同，用于存储前缀表。j 为 -1。j 用于追踪最长相等前缀的最后一个字符的位置。处理第一个字符：
next[0] 设置为 -1。这是因为第一个字符没有前缀和后缀，所以默认值是 -1。遍历模式串：
1 开始）。needle[i]：
needle[i] 与 needle[j + 1] 不匹配，并且 j 不等于 -1，则将 j 更新为 next[j]。这一步是寻找当前位置之前的子串的次长相等前缀和后缀。needle[i] 与 needle[j + 1] 匹配时，增加 j（j++），意味着我们找到了更长的相等前缀和后缀。j 存入 next[i]。next[i] 表示 needle 中以 i 结尾的子串的最长相等前后缀的长度。假设模式串 needle 为 "ABABC"，构建其前缀表的过程如下：
next = [-1]，j = -1。i = 1 (B)，needle[i] != needle[j + 1]，所以 next[1] = 0。i = 2 (A)，needle[i] != needle[j + 1]，所以 next[2] = 0。i = 3 (B)，needle[i] == needle[j + 1]，所以 j++ 并 next[3] = 1。i = 4 (C)，needle[i] != needle[j + 1]，所以 next[4] = 0。最终，前缀表 next 为 [-1, 0, 0, 1, 0]
KMP 算法主体：
j = -1。haystack：
haystack 的位置 0（字符 'a'）与 needle 的位置 0（字符 'a'）匹配时，j 变为 0。haystack 的位置 4（字符 'b'）与 needle 的位置 4（字符 'c'）不匹配。j。在前缀表中，next[3] 是 1，所以 j 变为 1。haystack，每次匹配失败时根据前缀表回溯 j。找到匹配：
j 达到 needle.length - 1，这意味着我们找到了完整的匹配。haystack 的位置 9（字符 'b'）匹配成功时，我们发现 j 为 8（needle.length - 1）。needle 长度加 1，即 9 - 9 + 1 = 1。假设我们有以下字符串：
haystack: "ABCABDABCD"
needle: "ABD"并且假设 needle 的前缀表 next 已经被计算为 [0, 0, 1]。
我们的目标是找到 needle 在 haystack 中第一次出现的位置。
初始化 j:
j = -1 表示当前在 needle 中匹配的位置。遍历 haystack:
for (let i = 0; i < haystack.length; ++i) { ... } 循环遍历主字符串 haystack。比较字符并更新 j:
while (j >= 0 && haystack[i] !== needle[j + 1]) j = next[j];haystack 和 needle 当前位置的字符不匹配时，使用前缀表 next 更新 j。这是为了找到 needle 中下一个可能的匹配位置。if (haystack[i] === needle[j + 1]) j++;j 递增以继续匹配下一个字符。检查是否找到完整匹配:
if (j === needle.length - 1) return (i - needle.length + 1);j 等于 needle 的长度减 1，这意味着找到了完整的匹配。返回匹配的起始位置。返回结果:
haystack 后没有找到匹配，则返回 -1。haystack 的过程中，算法比较每个字符并根据 needle 的前缀表来调整匹配位置。haystack 中到达索引 2 (C) 时，与 needle 中的索引 2 (D) 不匹配。根据前缀表，j 更新为 0 (next[1])。haystack 索引 4 (D)，算法发现匹配，此时 j 为 2，匹配成功。4 - 3 + 1 = 2，表示 needle 在 haystack 中的起始位置是 2。strStr 函数返回 1，表示 needle 在 haystack 中第一次出现的位置是索引 1。
这个示例展示了 KMP 算法如何在主字符串 haystack 中高效地搜索子串 needle。通过前缀表，算法能够在不匹配时快速跳到正确的位置，避免了从头开始的重复比较，显著提高了搜索效率。
时间复杂度是 O(n^2)
var repeatedSubstringPattern = function (s) {
const n = s.length;
for (let i = 1; i * 2 <= n; i++) {
if (n % i === 0) {
let match = true;
for (let j = i; j < n; j++) {
if (s[j] !== s[j - i]) {
match = false;
break;
}
}
if (match) return true;
}
}
return false;
};"abc" 的前缀可以是 "a", "ab" 或者整个字符串 "abc" 本身。"abc" 的后缀可以是 "c", "bc" 或者整个字符串 "abc" 本身。"abab"，最长相同前后缀是 "ab"，因为 "ab" 既是开头的前缀，也是结尾的后缀。