Cod sursa(job #1826929)

Utilizator cipri321Marin Ciprian cipri321 Data 11 decembrie 2016 09:13:00
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <fstream>
#include <cstring>
#define LIM 2000001
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
char T[LIM],P[LIM],S[2*LIM];
int i,r,s,p,k;
int A[2*LIM],REZ[LIM];
int main()
{
	fi.getline(P,LIM);
	fi.getline(T,LIM);
	strcpy(S,P);
	strcat(S,"*");
	strcat(S,T);
	s=strlen(S);
	p=strlen(P);
	A[0]=0;
	for(i=1;i<s;i++)
	{
		r=A[i-1];
		while(r>0)
		{
			if(S[i]==S[r])
				break;
			else
				r=A[r-1];
		}
		if(S[i]==S[r])
			A[i]=r+1;
		else
			A[i]=r;
	}
	for(i=0;i<s;i++)
		if(A[i] == p)
			REZ[++k]=i-2*p;
	fo<<k<<"\n";
	for(i=1;i<=min(1000,k);i++)
		fo<<REZ[i]<<" ";
	
	fi.close();
	fo.close();
	return 0;
}