【力扣刷题】Day09——字符串专题

---

上一篇文章：【力扣刷题】Day08——字符串专题_塔塔开!!!的博客-CSDN博客

5. 找出字符串中第一个匹配项的下标（kmp）

关于KMP算法的具体解释：

回顾以前的博客：字符串匹配 - 时间最考验人 - 博客园 (cnblogs.com)

核心总结：

• next[j]：存的是模式串s[j]最长相等前后缀的长度，当某一时刻不匹配时j就会跳到next[j]（最优）,直到找到或者j退无可退（0）
• KMP匹配的过程和求next[j]是极其相似的

KMP模板（下标从1开始）：

// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i ++ )
{
    while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j ++ ;
    ne[i] = j;
}

// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++ ;
    if (j == m)
    {
        j = ne[j];
        // 匹配成功后的逻辑
        // cout << i - m << " " // 匹配成功的起始位置
    }
}

题目链接：28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）

思路一：枚举（双指针），模拟，枚举原串 original 中的每个字符作为「发起点」，每次从原串的「发起点」和匹配串的「首位」开始尝试匹配

Code

class Solution {
    public int strStr(String haystack, String needle) {
        char[] original = haystack.toCharArray();
        char[] target = needle.toCharArray();
        int n = original.length;
        int m = target.length;

        for(int i = 0; i <= n - m; i ++){// n - m：保证原串够目标串进行遍历
            int a = i;
            int b = 0;
            while(b < m && original[a] == target[b]){
                a ++;
                b ++;
            }
            if(b == m) return i;
        }
        return -1;
    }
}

思路二：KMP算法匹配

Code

class Solution {
    // ss文本串 pp模式串
    public int strStr(String ss, String pp) {
        if(pp.isEmpty()) return 0;

        // 分别读取原串和匹配串的长度
        int n = ss.length(), m = pp.length();
        // 原串和匹配串前面都加空格，使其下标从 1 开始
        ss = " " + ss;
        pp = " " + pp;

        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();
        int[] ne = new int[m + 1];

        // 求next[j]
        for(int i = 2, j = 0; i <= m; i ++){
            while(j != 0 && p[i] != p[j + 1]) j = ne[j];
            if(p[i] == p[j + 1]) j ++;
            ne[i] = j;
        }
        
        // 匹配过程
        for(int i = 1, j = 0; i <= n; i ++){
            while(j != 0 && s[i] != p[j + 1]) j = ne[j];
            if(s[i] == p[j + 1]) j ++;
            if(j == m){
                j = ne[j];
                return i - m;
            }
        }
        return -1;
    }
}

6. 重复的子字符串（kmp）

题目链接：459. 重复的子字符串 - 力扣（LeetCode）

在由重复子串组成的字符串中，最长相等前后缀不包含的子串就是最小重复子串，这里那字符串s：abababab 来举例，ab就是最小重复单位。

如果最长的前后缀存在，且整个串的长能够整除最小重复子串的长度，说明改串可以由这个最小重复子串构成！

Code

class Solution {
    public boolean repeatedSubstringPattern(String ss) {
        int n = ss.length();
        ss = " " + ss;
        char[] s = ss.toCharArray();
        int[] ne = new int[n + 1];
		
        // 求next[j]
        for(int i = 2, j = 0; i <= n; i ++){
            while(j != 0 && s[i] != s[j + 1]) j = ne[j];
            if(s[i] == s[j + 1]) j ++;
            ne[i] = j;
        }

        
        int len = n;
        int max_fix = ne[len];// 获取最长相等前后缀 长度
        int re_len = len - max_fix;// 获取最小重复串的长度
        if(max_fix != 0 && len % re_len == 0){// 判断整个串是否能被最小重复串覆盖
            return true;
        }
        return false;
    }
}