Cod sursa(job #731636)

Utilizator paul_gabryelPaul Buda paul_gabryel Data 8 aprilie 2012 17:26:14
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb

#include <cstdio>
#include <fstream>
#include <string>
#include <algorithm>

using namespace std;

string a,b;
int p[2000001],poz[1024],n;

void read ()
{
	string s;
	ifstream in ("strmatch.in");
	in>>s;
	a=" "+s;
	in>>s;
	b=" "+s;
}

void solve ()
{
	p[1]=0;
	for(size_t i=2,q=0;i<a.size();++i)
	{
		for(;q&&a[q+1]!=a[i];q=p[q]);
		if(a[q+1]==a[i])
			++q;
		p[i]=q;
	}
	for(size_t i=1,q=0;i<b.size();++i)
	{
		for(;q&&a[q+1]!=b[i];q=p[q]);
		if(a[q+1]==b[i])
			++q;
		if(q+1==a.size())
		{
			q=p[a.size()-1];
			++n;
			if(n<=1000)
				poz[n]=i-a.size()+1;
		}
	}
}

void out ()
{
	freopen ("strmatch.out","w",stdout);
	printf("%d\n",n);
	for(int i=1;i<=min(1000,n);++i)
		printf("%d ",poz[i]);
}

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