引入

KMP是一种字符串匹配算法，可以在将近线性的时间复杂度内进行字符串匹配。

此类问题通常有一个文本串 $S$ 和一个模式串 $P$ 构成，说白了就是在 $S$ 中匹配 $T$，S.find(T)。

不难打出一个暴力程序，原理是枚举 $S$ 中开始时匹配的位置，逐位匹配字符。设 $|S|=n,|T|=m$，则暴力的时间复杂度为 $O(nm)$，代码如下。

int compare(string S,string T)
{
	int n=S.size(),m=T.size();
	for(int i=0;i<n-m+1;i++)
	{
		bool fl=1;
		for(int j=0;j<m;j++)
		{
			if(S[i+j]!=T[j])
			{
				fl=0;
				break;
			}
		}
		if(fl)
		 return i;
	}
	return -1;
}//返回第一次匹配成功在S中的下标

思想