Cod sursa(job #156162)

Utilizator M@2Te4iMatei Misarca M@2Te4i Data 12 martie 2008 13:15:44
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include<stdio.h>
#include<cstring>
#define vv 2000005

int n,m,p[vv],q,s[vv];
char a[vv],w[vv];

void citire(int &n, char a[])
{
	//scanf("%d",&n);
	//for (int i=0; i<n; i++)
//		scanf("%d",&a[i]);
    fgets(a,vv,stdin);
    if (a[strlen(a)-1]=='\n')
        a[strlen(a)-1]=0;
    n=strlen(a);
}

void prec()
{
	int k=0;
	p[0]=0;
	for (int i=2; i<=m; i++)
	{
		while (k>0 && w[k+1]!=w[i])
			k=p[k];
		if (w[k+1]==w[i])
			++k;
		p[i]=k;
	}
}

void kmp()
{
	for (int i=0; i<n; i++)
	{
		while (q>0 && w[q+1]!=a[i])
			q=p[q];
		if (w[q+1]==a[i])
			++q;
		if (q==m)
            s[++s[0]]=i-m+1;
	}
}

int main()
{
	freopen("strmatch.in","r",stdin);
	citire(m,w);
	citire(n,a);
    for (int i=n; i; --i)
        a[i]=a[i-1];
    a[0]=' ';
    for (int i=m; i; --i)
        w[i]=w[i-1];
    w[0]=' ';
	fclose(stdin);
	prec();
	kmp();
	printf("%d\n",s[0]);
	for (int i=1; i<=s[0]; i++)
        printf("%d ",s[i]);
	return 0;
}