当前位置：首页 > news >正文

【2024.01.04】转行小白-刷算法08

news 来源：原创 2024/5/14 21:02:09

可恶每天都起的很晚，研究生还是研究死啊

学习计划

1.每天刷3道算法

28找出字符串中第一个匹配项的下标

2.刷面试题

3.构建论文框架

1.28找出字符串中第一个匹配项的下标

28. 找出字符串中第一个匹配项的下标

var strStr = function (haystack, needle) {// 考虑特殊情况字串为空的时候if (needle.length === 0)return 0;// 下面这个方法是用来制造前缀表const getNext = (needle) => {// next储存前缀表let next = [];// 初始值为-1let j = -1;// 把初始值放进数组中next.push(j);// 遍历字串for (let i = 1; i < needle.length; ++i) {while (j >= 0 && needle[i] !== needle[j + 1])// 当前后缀不相等的时候j = next[j];// 当前后缀相等的时候，加1if (needle[i] === needle[j + 1])j++;next.push(j);}// 返回最后next的长度return next;}let next = getNext(needle);let j = -1;// 开始遍历 haystackfor (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算法

1.1KMP有什么用

KMP主要应用在字符串匹配上

1.2KMP相关概念

前缀表
- 前缀表（Prefix Table）通常是在字符串处理中使用的一种数据结构，尤其是在字符串匹配算法（如 KMP 算法）中。它的主要目的是为了提高字符串搜索的效率
- 前缀表：这是一个数组，用于存储字符串中每个位置的前缀匹配信息。在不同的上下文中，前缀表可能有不同的具体含义
前缀表在 KMP 算法中的应用

在 KMP（Knuth-Morris-Pratt）字符串匹配算法中，前缀表用于存储“部分匹配值”（Partial Match Table），这些值表示字符串中每个位置的最长相等的真前缀和真后缀的长度。例如：
- 对于字符串 "ABABC"，前缀表是 [0, 0, 1, 2, 0]。
- 意味着，到第 2 个位置（"ABA"）时，最长的相等的真前缀和真后缀是 "A"，其长度为 1。
- 使用前缀表的优点是，在 KMP 算法中匹配失败时，我们可以使用这个表来跳过不必要的比较。

1.3示例

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 中第一次出现的位置。
  
  KMP 算法步骤
- 初始化 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。通过前缀表，算法能够在不匹配时快速跳到正确的位置，避免了从头开始的重复比较，显著提高了搜索效率。

459.重复的子字符串

第一种解法：暴力解法

时间复杂度是 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;
};

第二种解法：KMP

前缀：一个字符串的前缀是指从字符串开头开始到任意位置的子串。例如，字符串 "abc" 的前缀可以是 "a", "ab" 或者整个字符串 "abc" 本身。
后缀：一个字符串的后缀是指从任意位置到字符串末尾的子串。例如，字符串 "abc" 的后缀可以是 "c", "bc" 或者整个字符串 "abc" 本身。
最长相同前后缀：指的是在不考虑整个字符串的情况下，字符串中最长的、相同的前缀和后缀。例如，对于字符串 "abab"，最长相同前后缀是 "ab"，因为 "ab" 既是开头的前缀，也是结尾的后缀。