跳至主要內容

前缀函数与 KMP 算法

2023年12月17日大约 4 分钟

前缀函数与 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;  } }

（全文完）