Cod sursa(job #1012561)

Utilizator contulmeuMunteanu Vasile contulmeu Data 19 octombrie 2013 12:39:07
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include<stdio.h>
#include<string.h>

using namespace std;
#define Nmax 2000005

char s[Nmax],p[Nmax];
int k, m, n,D[Nmax],px[Nmax];
void citire()
{
	freopen("strmatch.in","r",stdin);

	s[0]=p[0]=' ';

     gets(s+1);
     gets(p+1);

    fclose(stdin);

	n=strlen(s+1);
	m=strlen(p+1);
}



void prefix(char s[])
{
	int i;
	px[1]=0;
k=0;
	for(i=2;i<=n;++i)
	{
		//k=px[i-1];

		while(k>0&&s[k+1]!=s[i])
			k=px[k];

		if(s[k+1]==s[i])
		    k++;

		px[i]=k;

	//	 printf("%c\n", s[i]);

	}


}

void kmp(char s[], char p[])
{
	int i;

	prefix(s);


	k=0;
	for(i=1;i<=m;i++)
	{
		while(k>0&&s[k+1]!=p[i])
			k=px[k];

		if(s[k+1]==p[i])
			k++;

		if(k==n)
		{
			 D[++D[0]]=i-n;
			//k=px[k];
		}
	}

}


void afisare()
{
	int i;
	freopen("strmatch.out","w",stdout);
	  printf("%d\n", D[0]);
	  int pana=D[0];
   if(D[0]>1000)
    pana=1000;
	for(i=1;i<=pana;i++)
	  printf("%d ",D[i]);
printf("\n");
	fclose(stdout);

}

int main()
{
	citire();

	prefix(s);

	kmp(s,p);
	afisare();
	return 0;
}