Cod sursa(job #409148)

Utilizator alex@ndraAlexandra alex@ndra Data 3 martie 2010 14:39:15
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include<stdio.h>
#include<string.h>
#include<fstream>
using namespace std;
#define Nmax 2000001

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 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<=n;i++)
	{
		while(k>0&&s[k+1]!=p[i])
			k=px[k];
		
		if(s[k+1]==p[i])
			k++;
		
		if(k==m)
		{
			found(i-m);
			k=px[k];
		}
	}
	
}


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

}

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