KMP算法
#include
#define INF 0x3f3f3f3f3f3f3f3f
#define mod 1000000007
#define IOS ios::sync_with_stdio(false)
#define endl '\n'
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
string ptr, str;
int net[maxn];
void Get_Next() {//求next数组（kmp算法的关键之处）
int i = 0, j = -1;
net[i] = j;
while (i < ptr.size()) {
if (j == -1 || ptr[i] == ptr[j])net[++i] = ++j;
else j = net[j];
}
}
int Kmp_Search1() {//求目标串str中模式串ptr第一次出现的位置
Get_Next();
int i = 0, j = 0;
while (i < str.size() && j < ptr.size()) {
if (j == -1 || ptr[j] == str[i])++i, ++j;
else j = net[j];
}
if (j == ptr.size())return i - j + 1;
return -1;//表示没有找到
}
int Kmp_Search2() {//求目标串str中模式串ptr出现的次数
int i = 0, j = 0;
int ans = 0;
while (i > ptr >> str;
cout << Kmp_Search1() << endl;
cout << Kmp_Search2();
}
作者：zzqwtc
