题解 | #String Matching# 两种方法
String Matching
https://www.nowcoder.com/practice/00438b0bc9384ceeb65613346b42e88a
- 分别使用暴力算法、KMP算法求解
- 在main()函数实现调用
#include <iostream> #include <bits/stdc++.h> using namespace std; //1、经典暴力算法 int BF(string text, string pattern) { int sum = 0; for (int pos = 0; pos < text.length() - pattern.length() + 1; pos++) { int flag = 1; // 从 pos 开始,检查是否与 pattern 匹配 for (int i = 0; i < pattern.length(); i++) { if (text[pos + i] != pattern[i]) { flag = 0; break; } } if (flag) sum++; } return sum; } // 2、KMP数组 int* getNext(string pattern) { // 使用 DP 求解 next 数组 int* next = new int[pattern.length()]; next[0] = -1; int i = 0, j = -1; // i为当前主串正在匹配的位置,也是 next 数组的索引 while (i < pattern.length()) { if (j == -1 || pattern[i] == pattern[j]) next[++i] = ++j; else j = next[j]; } return next; } int KMP(string text, string pattern) { int* next = getNext(pattern); int sum = 0, j = -1; // 初始化 j 为-1 for (int i = 0; i < text.length(); i++) { //匹配text[i] while (j != -1 && text[i] != pattern[j + 1]) { //j+1? j = next[j]; // 回退,更新模式串指针 } if (text[i] == pattern[j + 1]) { // 匹配成功,令j加1 j++; } if (j == pattern.length() - 1) { // 完全匹配,说明找到了一个子串 sum++; j = next[j]; // j 回退,继续匹配 } } delete[] next; // 释放内存空间 return sum; } int main() { string text, pattern; while (cin >> text >> pattern) { int sum; sum=BF(text, pattern); // sum=KMP(text,pattern); cout << sum << endl; } return 0; }