Cod sursa(job #579618)

Utilizator marius21Petcu Marius marius21 Data 12 aprilie 2011 12:20:37
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <cstdio>
#include <cstdlib>
#include <cstring>

FILE *fin=fopen("strmatch.in","r");
FILE *fout=fopen("strmatch.out","w");

char s[2000001],w[2000001];
int n,m;
int t[2000001];

void compute_t()
{
	int i = 2;
	int cnd = 0;
	t[0]=-1;
	t[1]=0;
	while (i<=m)
	{
		if (w[i-1]==w[cnd])
		{
			cnd++;
			t[i]=cnd;
			i++;
		} else 
			if (cnd)
				cnd=t[cnd];
			else
				t[i++] = 0;
	}
}

int sn = 0;
int sol[1000];

void solution(int pos)
{
	if (sn<1000)
		sol[sn]=pos;
	sn++;
}

void kmp()
{
	int st = 0;
	int i = 0;
	while (st+i<n)
	{
		if (i<m && w[i]==s[st+i])
		{
			i++;
			if (i==m)
				solution(st);
		} else {
			st=st+i-t[i];
			if (t[i]<0)
				i=0;
			else
				i = t[i];
		}
	}
}

int main (int argc, char * const argv[]) {
	fscanf(fin, "%s%s",s,w);
	n = strlen(s);
	m = strlen(w);
	compute_t();
	kmp();
	fprintf(fout, "%d\n",sn);
	if (sn>1000)
		sn=1000;
	for (int i=0; i<sn; i++)
		fprintf(fout, "%d ",sol[i]);
	fclose(fin);
	fclose(fout);
    return 0;
}