KMP

学习了 KMP(Knuth-Morris-Pratt) 字符串匹配算法，记录下代码。

public class KMP { private int[][] dp; private String pat; public KMP(String pat) { this.pat = pat; int M = pat.length(); // dp[状态][字符] = 下个状态 dp = new int[M][256]; // base case dp[0][pat.charAt(0)] = 1; // 影子状态 X 初始为 0 int X = 0; // 构建状态转移图（稍改的更紧凑了） for (int j = 1; j < M; j++) { for (int c = 0; c < 256; c++) { dp[j][c] = dp[X][c]; dp[j][pat.charAt(j)] = j + 1; // 更新影子状态 X = dp[X][pat.charAt(j)]; } } public int search(String txt) { int M = pat.length(); int N = txt.length(); // pat 的初始态为 0 int j = 0; for (int i = 0; i < N; i++) { // 计算 pat 的下一个状态 j = dp[j][txt.charAt(i)]; // 到达终止态，返回结果 if (j == M) return i - M + 1; } // 没到达终止态，匹配失败 return -1; } }

 运用KMP：

#include<bits/stdc++.h> using namespace std; const int maxn = 10010; int dp[maxn][256]; string pat; string txt; void kmp() { int M = pat.length(); dp[0][pat[0]] = 1; int X = 0; for(int j = 1; j < M; ++j) { for(int c = 0; c < 256; ++c) { if (pat[j] == c) dp[j][c] = j + 1; else dp[j][c] = dp[X][c]; } X = dp[X][pat[j]]; } } int search() { int M = pat.length(); int N = txt.length(); int j = 0; for(int i = 0; i < N; ++i) { j = dp[j][txt[i]]; if(j == M) return i - M + 1; } return -1; } int main() { cin >> pat; kmp(); cin >> txt; while(txt != "") { int pos = search(); if(pos == -1) cout << "不匹配\n"; else cout << "首次匹配位置在" << pos << endl; cin >> txt; } }

可以参考一下https://mp.weixin.qq.com/s/kCjRuY6ygYJWWX5HPVLa5A讲的真好。