Cod sursa(job #1805372)

Utilizator marcdariaDaria Marc marcdaria Data 13 noiembrie 2016 18:33:33
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include<stdio.h>
#include<string.h>

using namespace std;
#define Nmax 2000001

char s[Nmax],p[Nmax];
int k, m, n,D[1001],px[1001];
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 found(int d)
{
	D[0]=D[0]+1;

	if(D[0]<=1000)
	  D[D[0]]=d;
}

void prefix(char s[])
{
	int i;
	px[1]=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;
	}


}

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)
		{
			found(i-n);
			k=px[k];
		}
	}

}


void afisare()
{
	int i;
	freopen("strmatch.out","w",stdout);
	  printf("%d\n", D[0]);

	for(i=1;i<=D[0];i++)
	  printf("%d ",D[i]);

	fclose(stdout);

}

int main()
{
	citire();
	kmp(s,p);
	afisare();
	return 0;
}