KMP：字符串匹配

算法理解

KMP 的核心是 next 数组：当模式串在位置 j 失配时，next[j - 1] 告诉我们有多长的前后缀可直接复用，所以文本指针不用回退。

• 适用：单模式串匹配、循环节、前后缀问题。
• 复杂度：构建 next 为 O(m)，匹配为 O(n)。
• 注意：空模式串应先特判；找全部匹配时命中后不能直接结束。

模板代码

#include <bits/stdc++.h>
using namespace std;
void getnext(const string &str,vector<int> &n)
{
	int i=1;
	int j=0;
	n.push_back(0);
	while (i<(int)str.size())
	{
		if (str[i]==str[j])
		{
			j++;
			n.push_back(j);
			i++;
		}
		else 
		{
			if (j==0)
			{
				i++;
				n.push_back(0);
			}
			else 
			{
				j=n[j-1];
			}
		}
	}
}
int kmp(const string &str, const string &zc, const vector<int> &n)
{
	int i=0;
	int j=0;
	while (i<(int)str.size())
	{
		if (str[i]==zc[j])
		{
			i++;
			j++;
		}
		else
		{
			if (j==0)
			{
				i++;
			}
			else 
			{
				j=n[j-1];

			}
		}
		if (j==(int)zc.size())
		{
			return i-j;
		}
	}
	return -1;
}
int main()
{
	string s1,s2;
	cin>>s1>>s2;
	vector<int>n;
	getnext(s2, n);
	int ans=kmp(s1,s2, n);
	cout<<ans;
	return 0;
}