【算法随想录04】KMP 字符串匹配算法

这是字符串模式匹配经典算法。

给定一个文本 t 和一个字符串 s，我们尝试找到并展示 s 在 t 中的所有出现（occurrence）。

#include<bits/stdc++.h>using namespace std;vector<int> KMP(string s) {int n = s.size();vector<int> ans(n, -1);int j = 0;for(int i = 1; i < n; i++) {j = ans[i - 1];while(j >= 0 && s[i] != s[j]) j = ans[j];if(j >= 0) ans[i] = j + 1;}return ans;
}int main() {string s1;string s2;cout << "主串：";cin >> s1;cout << "子串：";cin >> s2;vector<int> pi = KMP(s2);int a = s1.size(), b = s2.size();int i = 0, j = 0;while(i < a && j < b) {if(j == -1) {i++;j++;}if(s1[i] == s2[j]) {i++;j++;} else j = pi[j];}if(j==b) cout << s1 << "是" << s2 << "的主串" << endl;return 0;
}