Cod sursa(job #570994)

Utilizator yaxleyyaxley yaxley Data 3 aprilie 2011 20:46:59
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include<string.h>
#include<stdio.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++)
	{k=p[i-1];
		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&&nr<1000;i++)
	{
		while(k > 0 && s[k + 1]!=a[i])
			k = p[k];
		
		if(s[k + 1] == a[i])
			 k = k + 1;
		
		if(k==n-1)
			{ 	nr++;
				d[nr]=i-n+1;
			}	k=p[k];
		
	}
}
	
int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	fgets(s+1,2000002,stdin);
	fgets(a+1,2000002,stdin);
	
	
	 n = strlen(s+1);
	 m = strlen(a+1);
	
	calculprefix();
	
	kmp();
	printf("%d",nr);
	for(int i=1;i<=nr;i++)
	printf("%d ",d[i]);
	
	return 0;
}