前缀函数与 KMP 算法

• OI Wiki: https://oi-wiki.org/string/kmp/

题目	难度
28. 找出字符串中第一个匹配项的下标	简单
214. 最短回文串	困难
459. 重复的子字符串	简单
1392. 最长快乐前缀	困难
1397. 找到所有好字符串	困难	数位 DP
2851. 字符串转换	困难

前缀函数

vector<int> prefix_function(string s) {
  int n = (int)s.length();
  vector<int> pi(n);
  for (int i = 1; i < n; i++) {
    int j = pi[i - 1];
    while (j > 0 && s[i] != s[j]) j = pi[j - 1];
    if (s[i] == s[j]) j++;
    pi[i] = j;
  }
  return pi;
}

private int[] prefix_function(char[] s) {
    int n = s.length;
    int[] pi = new int[n];
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
        if (s[i] == s[j]) j++;
        pi[i] = j;
    }
    return pi;
}

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

public class Solution28 {
    public int strStr(String haystack, String needle) {
        char[] txt = haystack.toCharArray();
        char[] pat = needle.toCharArray();
        int n = txt.length, m = pat.length;

        int[] pi = prefix_function(pat);
        for (int i = 0, j = 0; i < n; i++) {
            while (j > 0 && txt[i] != pat[j]) j = pi[j - 1];
            if (txt[i] == pat[j]) j++;
            if (j == m) {
                return i - m + 1;
            }
        }
        return -1;
    }

    private int[] prefix_function(char[] s) {
        int n = s.length;
        int[] pi = new int[n];
        for (int i = 1; i < n; i++) {
            int j = pi[i - 1];
            while (j > 0 && s[i] != s[j]) j = pi[j - 1];
            if (s[i] == s[j]) j++;
            pi[i] = j;
        }
        return pi;
    }

    public int strStr2(String haystack, String needle) {
        return haystack.indexOf(needle);
    }
}

214. 最短回文串

给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。

public class Solution214 {
    public String shortestPalindrome(String s) {
        int n = s.length();
        // s 的反序
        String rev = new StringBuilder(s).reverse().toString();
        char[] txt = rev.toCharArray();
        char[] pat = s.toCharArray();

        int[] pi = prefix_function(pat);
        int j = 0;
        for (int i = 0; i < n; i++) {
            while (j > 0 && txt[i] != pat[j]) j = pi[j - 1];
            if (txt[i] == pat[j]) j++;
        }
        return rev + s.substring(j);
    }

    private int[] prefix_function(char[] s) {
        int n = s.length;
        int[] pi = new int[n];
        for (int i = 1; i < n; i++) {
            int j = pi[i - 1];
            while (j > 0 && s[i] != s[j]) j = pi[j - 1];
            if (s[i] == s[j]) j++;
            pi[i] = j;
        }
        return pi;
    }
}

459. 重复的子字符串

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

public class Solution459 {
    public boolean repeatedSubstringPattern(String s) {
        int n = s.length();
        char[] txt = (s.substring(1) + s.substring(0, n - 1)).toCharArray();
        char[] pat = s.toCharArray();

        int[] pi = prefix_function(pat);
        for (int i = 0, j = 0; i < txt.length; i++) {
            while (j > 0 && txt[i] != pat[j]) j = pi[j - 1];
            if (txt[i] == pat[j]) j++;
            if (j == n) {
                return true;
            }
        }
        return false;
    }

    private int[] prefix_function(char[] s) {
        int n = s.length;
        int[] pi = new int[n];
        for (int i = 1; i < n; i++) {
            int j = pi[i - 1];
            while (j > 0 && s[i] != s[j]) j = pi[j - 1];
            if (s[i] == s[j]) j++;
            pi[i] = j;
        }
        return pi;
    }
}

1392. 最长快乐前缀

「快乐前缀」 是在原字符串中既是 非空 前缀也是后缀（不包括原字符串自身）的字符串。

给你一个字符串 s，请你返回它的 最长快乐前缀。如果不存在满足题意的前缀，则返回一个空字符串 "" 。

public class Solution1392 {
    public String longestPrefix(String s) {
        int n = s.length();
        int[] pi = prefix_function(s.toCharArray());
        return s.substring(0, pi[n - 1]);
    }

    private int[] prefix_function(char[] s) {
        int n = s.length;
        int[] pi = new int[n];
        for (int i = 1; i < n; i++) {
            int j = pi[i - 1];
            while (j > 0 && s[i] != s[j]) j = pi[j - 1];
            if (s[i] == s[j]) j++;
            pi[i] = j;
        }
        return pi;
    }
}

2851. 字符串转换

kmp 求循环字符串 text 中，pattern 出现的次数。

public class Solution2851 {
    private static final int MOD = (int) (1e9 + 7);

    public int numberOfWays(String s, String t, long k) {
        int n = s.length();
        int c = kmpSearch(s + s.substring(0, n - 1), t);
        long[][] mat = {{c - 1, c}, {n - c, n - 1 - c}};
        long[][] mPowN = matQuickPow(mat, k);
        return (int) (s.equals(t) ? mPowN[0][0] : mPowN[0][1]);
    }

    private int[] prefix_function(char[] s) {
        int n = s.length;
        int[] pi = new int[n];
        for (int i = 1; i < n; i++) {
            int j = pi[i - 1];
            while (j > 0 && s[i] != s[j]) j = pi[j - 1];
            if (s[i] == s[j]) j++;
            pi[i] = j;
        }
        return pi;
    }

    private int kmpSearch(String text, String pattern) {
        char[] txt = text.toCharArray();
        char[] pat = pattern.toCharArray();

        int[] pi = prefix_function(pat);
        int matchCnt = 0;
        for (int i = 0, j = 0; i < txt.length; i++) {
            while (j > 0 && txt[i] != pat[j]) j = pi[j - 1];
            if (txt[i] == pat[j]) j++;
            if (j == pat.length) {
                matchCnt++;
                j = pi[j - 1];
            }
        }
        return matchCnt;
    }

    // 矩阵快速幂 res = a^n
    private long[][] matQuickPow(long[][] a, long n) {
        int len = a.length;
        // 对角矩阵
        long[][] res = new long[len][len];
        for (int i = 0; i < len; i++) {
            res[i][i] = 1;
        }
        while (n > 0) {
            if ((n & 1) == 1) {
                res = matMulti(res, a);
            }
            n >>= 1;
            a = matMulti(a, a);
        }
        return res;
    }

    // 矩阵快速幂 res = a * b
    private long[][] matMulti(long[][] a, long[][] b) {
        int n = a.length;
        long[][] res = new long[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    res[i][j] += a[i][k] * b[k][j] % MOD;
                    res[i][j] %= MOD;
                }
            }
        }
        return res;
    }
}

（全文完）