原理
代码
//顶级垃圾程序
//A very bad program
#include <bits/stdc++.h>
using namespace std;
vector<int> build_next(string p){
vector<int> _next;
_next.push_back(0); //next数组,先放一个0
int prefix_len = 0, i = 1, /*当前共同前后缀的长度*/p_len = p.length();
while (i < p_len){
if (p[prefix_len] == p[i]){ //如果下个字符仍然相同
prefix_len++; //代表可构成更长的前后缀,长度加1
_next.push_back(prefix_len);
i++;
} else { //如果不相同
if (!prefix_len){ //如果依然不存在
_next.push_back(0); //设为0
i++;
} else {
prefix_len = _next[prefix_len - 1]; //先看有没有更短的前后缀
}
}
}
return _next;
}
int kmp_search(string s, string p){ //返回起始位置
vector<int> _next = build_next(p); //构建next数组
int i = 0, j = 0, s_len = s.length(), p_len = p.length(); //双指针和主串与字串的长度
while (i < s_len){
if (s[i] == p[j]){ //如果相等
i++; //就继续比
j++;
} else if (j > 0) { //如果匹配失败
j = _next[j - 1]; //就根据next数组来跳过
} else i++; //如果第一个就匹配失败就只跳过一位
if (j == p_len) return i - j; //如果匹配成功,就返回起始位置
}
return -1;//如果匹配失败,就返回-1
}
int n, len;
string s, p;
int main(){
cin >> s >> p;
len = p.length();
n = kmp_search(s, p);
cout << n << endl;
return 0;
}
输入1:
ABABABCAA
ABABC
输出1:
2
输入2:
ABABABCAA
ABB
输出2:
-1