Cod sursa(job #1049890)

Utilizator rvnzphrvnzph rvnzph Data 7 decembrie 2013 21:53:00
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 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])
			if(pos>=0) lps[i]=lps[pos]+1;
			else lps[i]=0;
	}

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

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

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

	return 0;
}