Cod sursa(job #723972)

Utilizator ms-ninjacristescu liviu ms-ninja Data 26 martie 2012 08:50:40
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <string>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define NMax 2000005

int m, n;
char a[NMax], b[NMax];
int pi[NMax], pos[1024];
vector <int> sol;

void read()
{
	char c;
	while((c=fin.get()) && (c!='\n'))
		a[++n]=c;
	a[0]=' ';
	while((c=fin.get()) && (c!='\n') && (c!=EOF))
		b[++m]=c;
	b[0]=' ';
}

void make_prefix()
{
	int q=0,i;
	
	for(i=2;i<=n;++i)
	{
		while(q!=0 && a[q+1]!=a[i])
			q=pi[q];
		if(a[q+1]==a[i])
			++q;
		pi[i]=q;
	}
}

void solve()
{
	int i, q=0,nr=0;
	
	for(i=1;i<=m;++i)
	{
		while(q!=0 && a[q+1]!=b[i])
			q=pi[q];
		if(a[q+1]==b[i])
			++q;
		
		if(q==n)
		{
			q=pi[n];
			++nr;
			if(nr<=1000)
				pos[nr]=i-n;
		}
	}
	fout<<nr<<'\n';
	for(int k=1;k<=min(nr,1000);++k)
		fout<<pos[k]<<" ";
}
				

int main()
{
	read();
	make_prefix();
	solve();
	
	return 0;
}