Mai intai trebuie sa te autentifici.

Cod sursa(job #505699)

Utilizator stay_awake77Cangea Catalina stay_awake77 Data 3 decembrie 2010 17:39:53
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>

using namespace std;

char T[2000002],P[2000002];
int n,L[2000002],m,sol[1002],j;

void prefix()
{
	int i,k;
	
	L[1]=0;
	for (i=2; i<=n; 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;
	}
}

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

int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	fgets(P+1,2000002,stdin);
	fgets(T+1,2000002,stdin);
	n=strlen(P+1)-1;
	m=strlen(T+1)-1;
	
	prefix();
	rezolva();
	
	printf("%d\n",sol[0]);
	for(j=1;j<=min(sol[0],1000);j++)
		printf("%d ",sol[j]);
	
	return 0;
}