Cod sursa(job #2747640)

Utilizator AndreiCroitoruAndrei Croitoru AndreiCroitoru Data 29 aprilie 2021 15:17:08
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include <bits/stdc++.h>
/// folosind KMP
using namespace std;
int ans[2000001];
int pi[2000001];
	char a[2000005];
	char b[2000005];
int main()
{
	ifstream cin("strmatch.in");
	ofstream cout("strmatch.out");
	cin>>(a+1)>>(b+1);
	int n=strlen(a+1);
	int m=strlen(b+1);
	pi[1]=0;	
	int k=0;
	for(int i=2;i<=n;i++)
	{
		while((k>0) and (a[k+1]!=a[i]))
			k=pi[k];
		if(a[k+1]==a[i])
			k++;
		pi[i]=k;
	}
	k=0;
	int q=0;
	for(int i=1;i<=m;i++)
	{
		while((k>0) and a[k+1]!=b[i])
			k=pi[k];
		if(a[k+1]==b[i])
			k++;	
		if(k==n)
		{
			k=pi[n];
			ans[++q]=i-n;
		}
	}
	cout<<q<<'\n';
	int min_afis=min(q,1000);
	for(int i=1;i<=min_afis;i++)
	{
		cout<<ans[i]<<" ";
	}
}