Cod sursa(job #1134039)

Utilizator span7aRazvan span7a Data 5 martie 2014 22:19:28
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include<cstring>
#include<iostream>
#include<fstream>
using namespace std;
char s1[2000005],s2[2000005];
int sar[2000005],n1,n2,nr,sol[1008];

void completeaza()
{
	for(int i=2;i<=n1;i++)
		if(s1[i-1]==s1[sar[i-1]])
			sar[i]=sar[i-1]+1;
}
void kmp()
{
	int i,j,k=0,nrap=0;
	for(i=0;i<=n2;)
	{
		j=0;k=i;
		while(j<n1&&k<n2&&s2[k]==s1[j]){k++;j++;}
		if(j==n1){nr++;if(nr<=1000)sol[++nrap]=i;}
		i=k-sar[j];
	}
	cout<<nr<<'\n';
	for(i=1;i<=nrap;i++)
		cout<<sol[i]<<" ";

}
int main()
{
    	freopen("strmatch.in","r",stdin);
    	freopen("strmatch.out","w",stdout);
	sar[0]=-1;sar[1]=0;
	cin.getline(s1,2000005);
	cin.getline(s2,2000005);
	n1=strlen(s1);
	n2=strlen(s2);
	completeaza();
	kmp();
	return 0;
}