Cod sursa(job #1834030)

Utilizator MoleRatFuia Mihai MoleRat Data 23 decembrie 2016 18:37:36
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <fstream>
#include <string.h>
using namespace std;
char T[2000001],P[2000001];
char TT[4000002];
int FF[4000002];
int r,i,rez,n;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
int main()
{
	fi>>P;
	n=strlen(P);
	fi>>T;
	TT[0]='\0';
	strcat(TT,P);
	strcat(TT,"*");
	strcat(TT,T);
	FF[0]=0;
	for (i=1;TT[i]!='\0';i++)
	{
		r=FF[i-1];
		while (r>0)
		{
			if (TT[i]==TT[r])
				break;
			r=FF[r-1];
		}
		if (TT[i]==TT[r])
			FF[i]=r+1;
		else
			FF[i]=0;
	}
	rez=0;
	for (i=0;TT[i]!='\0';i++)
		if (FF[i]==n)
			rez++;
	fo<<rez<<"\n";
	for (i=0;TT[i]!='\0';i++)
		if (FF[i]==n)
			fo<<i-n-n<<" ";
	fi.close();
	fo.close();
	return 0;
}