Cod sursa(job #2280537)

Utilizator shantih1Alex S Hill shantih1 Data 10 noiembrie 2018 19:47:57
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <iostream>
#include <fstream>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int n,a,b;
int pi[200005],r[1005];
string A,B,s;

void prefix_func()
{
	pi[1]=0;
	int k=0;
	for(int q=2;q<=a;q++)
	{
		while(k>0 && A[k+1]!=A[q])	
			k=pi[k];
		if(A[k+1]==A[q])
			k++;
		pi[q]=k;
	}
}
void KMP_Matcher()
{
	prefix_func();
	int q=0;
	for(int i=1;i<=b;i++)
	{
		while(q>0 && A[q+1]!=B[i])
			q=pi[q];
		if(A[q+1]==B[i])
			q++;
		if(q==a-1)
		{
			n++;
			if(n<=1000)	r[n]=i-a+1;
			q=pi[q];
		}
	}
}
int main() {
	
	A=" ";	B=" ";
	getline(fin, s);
	A+=s;
	getline(fin, s);
	B+=s;
	
	a=(int)A.size();
	b=(int)B.size();
	if(a>b)
	{	fout<<0<<"\n";	return 0;	}
	if(A==B)
	{	fout<<1<<"\n"<<0<<"\n";	return 0;	}
	
	KMP_Matcher();
	
	fout<<n<<"\n";
	int l=min(n,1000);
	for(int i=1;i<=l;i++)
		fout<<r[i]<<" ";
}