Cod sursa(job #578136)

Utilizator petroMilut Petronela petro Data 11 aprilie 2011 01:32:45
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include<stdio.h>
#include<string.h>
#define M 2000003
using namespace std;

FILE *f=fopen("strmach.in","r");
FILE *g=fopen("strmach.out","w");

char s[M], t[M];
long lt,ls,l[M];
long long nr=0;
long poz[1002];

void pref()
{
	ls=strlen(s)-2;
	long i,k;
	l[1]=0;
	for(i=2;i<=ls;++i)
	{
		k=l[i-1];
		while(k>0 && s[k+1]!=s[i])
			k=l[k];
		if(s[k+1]==s[i])
			++k;
		l[i]=k;
	}
}

void kmp()
{
	lt=strlen(t)-2;
	long i,k;
	k=0;
	for(i=1;i<=lt;++i)
	{
		while(k>0 && s[k+1]!=t[i])
			k=l[k];
		if(s[k+1]==t[i])
			++k;
		if(k==ls)
		{
			nr++;
			if(nr<=1000)
				poz[nr]=i-k;
			k=l[k];
		}
	}
}

void afis()
{
	long long max,i;
	fprintf(g,"%lld\n",nr);
	
	max=nr;
	if(nr>1000) max=1000;
	for(i=1;i<=max;++i)
		fprintf(g,"%ld ",poz[i]);
}

int main()
{
	char w[M];
	fgets(s,M,f);
	strcpy(w,s);
	strcpy(s+1,w);
	fgets(t,M,f);
	strcpy(w,t);
	strcpy(t+1,w);
	pref();
	kmp();
	afis();
	fclose(g);
	fclose(f);
	return 0;
}