Cod sursa(job #920502)

Utilizator Kira96Denis Mita Kira96 Data 20 martie 2013 15:31:57
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.56 kb
#include<fstream>
#include<string.h>
#define DIM 2000010
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n,i,m,d[DIM],pi[DIM],k,v[DIM],t;
char s[DIM],p[DIM];
int main ()
{
	f>>(p+1);
	f>>(s+1);
	n=strlen(p+1);
	for(i=2;p[i];i++)
	{
		while(p[i]!=p[k+1]&&k)
		k=pi[k];
		if(p[i]==p[k+1]) ++k;
		pi[i]=k;
	}
	k=0;
	for(i=1;s[i];++i)
	{
		while(s[i]!=p[k+1]&&k)
		k=pi[k];
		if(s[i]==p[k+1]) ++k;
		d[i]=k;
		if(k==n)
		v[++t]=i-n;
	}
	g<<t<<"\n";
	for(i=1;i<=1000&&i<=t;++i)
	g<<v[i]<<" ";
	return 0;
}