Cod sursa(job #539389)

Utilizator balakraz94abcd efgh balakraz94 Data 22 februarie 2011 21:51:59
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include<cstdio>
#define l 2000001
using namespace std;

void citeste();
void rezolva();
void afiseaza();

int m,n;
char p[l],t[l];
short L[l];
int sol[1001];
int c=0;



void citeste()
{
	freopen("strmatch.in","r",stdin);
	
	char c;
	m=n=0;
	
	scanf("%c",&c);
	while(c!='\n')
	{
		p[++m]=c;
		scanf("%c",&c);
	}
	
	scanf("%c",&c);
	while(c!='\n')
	{
		t[++n]=c;
		scanf("%c",&c);
	}
	
	fclose(stdin);	
}


void rezolva()
{
	int k;
	
	L[1]=0;
	for(int i=2;i<=m;i++)
	{
		k=L[i-1];
		while(k>0 && p[k+1]!=p[i]) k=L[k];
		
		if(p[k+1]==p[i]) k++;
		
		L[i]=k;
	}
	
	k=0;
	
	for(int i=1;i<=n && c<1000;i++)
	{
		while(k>0 && p[k+1]!=t[i]) k=L[k];
		
		if(p[k+1]==t[i]) k++;
		
		if(k==m) sol[++c] = i-m;
	}
}



void afiseaza()
{
	freopen("strmatch.out","w",stdout);
	
	printf("%d\n",c);
	
	for(int i=1;i<=c;i++) printf("%d ",sol[i]);
	
	fclose(stdout);
}

int main()
{
	citeste();
	rezolva();
	afiseaza();
	
	return 0;
}