Cod sursa(job #1049930)

Utilizator rvnzphrvnzph rvnzph Data 7 decembrie 2013 22:29:46
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <stdio.h>
#include <cstring>

using namespace std;

const int strLEN=2000002;

char A[strLEN],B[strLEN];
int lps[strLEN-2];
int sol[strLEN-1];

int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);


	fgets(A,strLEN,stdin);
	fgets(B,strLEN,stdin);

	int nA=strlen(A)-1;
	int nB=strlen(B)-1;

	//longest prefix-suffix
	memset(lps,-1,sizeof(lps));

	int pos=-1;
	for(int i=1;i<nA;++i)
	{
		while(pos>=0&&A[pos+1]!=A[i]) pos=lps[pos];
		if(A[pos+1]==A[i]) ++pos;
		lps[i]=pos;
	}

	pos=-1;
	for(int i=0;i<nB;++i)
	{
		while(pos>=0&&B[i]!=A[pos+1]) pos=lps[pos];
		if(B[i]==A[pos+1]) ++pos;

		if(pos+1==nA)
		{
			sol[++sol[0]]=i-nA+1;
			pos=lps[pos];
		}
	}

	printf("%d\n",sol[0]);
	for(int i=1;i<=sol[0]&&i<=1000;++i)
		printf("%d ",sol[i]);
	printf("\n");

	return 0;
}