Cod sursa(job #570570)

Utilizator yaxleyyaxley yaxley Data 3 aprilie 2011 11:52:02
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include<string.h>
#include<fstream.h>
char s[2000002],a[2000002];
int p[2000003];
int d[2000003];
int n,m;
int nr=0;
void calculprefix()
{
	int k = 0;
	p[1] = 0;
	
	for(int i=2;i<=n;i++)
	{
		while(k > 0 && s[k + 1]!=s[i])
			k = p[k];
		
		if(s[k + 1] == s[i])
			 k = k + 1;
		
		p[i] = k;
	}
}

void kmp()
{
	int k=0;
	
	for(int i=1;i<=m;i++)
	{
		while(k > 0 && s[k + 1]!=a[i])
			k = p[k];
		
		if(s[k + 1] == a[i])
			 k = k + 1;
		
		if(k==n)
			{ 	nr++;
				d[nr]=i-n;
			}	
		
	}
}
	
int main()
{
	ifstream f("strmatch.in");
	ofstream g("strmatch.out");
	f.get(s+1,2000002);
	f.get();
	f.get(a+1,2000002);
	
	
	 n = strlen(s+1);
	 m = strlen(a+1);
	
	calculprefix();
	
	kmp();
	g<<nr<<"\n";
	for(int i=1;i<=nr;i++)
	g<<d[i]<<" ";
	
	return 0;
}