Cod sursa(job #723958)

Utilizator ms-ninjacristescu liviu ms-ninja Data 26 martie 2012 08:39:41
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 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;
	while((c=fin.get()) && (c!='\n') && (c!=EOF))
		b[++m]=c;
}

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=2;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)
				sol.push_back(i-n);
		}
	}
	
	fout<<sol.size()<<'\n';
	for(unsigned k=0;k<sol.size();++k)
		fout<<sol[k] <<" ";
}
				

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