RT,本人在写完next(KMP)数组,准备写KMP匹配之前，交了一发O(mn)纯暴力 没想到直接过了...

代码如下 可以看到 我还没有写KMP的跳转功能...

附本人评测记录 HERE

#include<bits/stdc++.h>
using namespace std;

const int N=1e6+50;

char target[N];
char storing[N];

int KMP[N];

int main()
{
	scanf("%s",target+1);
	scanf("%s",storing+1);
	
	int len1=0,len2=0;
	for (int i=1;i<=N;i++)//文本的长度
	{
		if (target[i]==0)
		{
			len1=i-1;
			break;
		}
	}
	for (int i=1;i<=N;i++)//匹配的长度
	{
		if (storing[i]==0)
		{
			len2=i-1;
			break;
		}
	}
	

	int j=0;
	for (int i=1;i<=len2;i++)//本质上是个预处理呢 
	{
		//开始计算KMP数组:前缀在哪里(最后一位)
		//当然，实际的移动距离是KMP[i]+1 因为当前的不可以！
	
		if (i==1)//只有一个元素的话
		{
			KMP[i]=0;
			continue;
		}
		
		while(j>0 && storing[i]!=storing[j+1])//一直往前翻相同前缀 直到没有
		{
			j=KMP[j];
		}
		
		if (storing[i]==storing[j+1]) j++;
		
		KMP[i]=j;
		
	}
	
	int l=1,r=1;
	while(r<=len1 && l<=len1)
	{
		
		bool isSame=1;
		while(r-l+1<=len2)
		{
			if (target[r]!=storing[r-l+1])
			{
				isSame=0;
				break;
			}
			r++;
		}
		
		if (isSame==1)
		{
			cout<<l<<'\n';
			l++;
			r=l;
		}
		else
		{
			l++;
			r=l;
		}
		
	}
	for (int i=1;i<=len2;i++) cout<<KMP[i]<<' ';//最后 输出KMP数组
	return 0;
}