原理

KMP算法视频

代码

//顶级垃圾程序
//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