Cod sursa(job #778900)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 16 august 2012 09:08:52
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include<iostream>
#include<fstream>
#include<string.h>
using namespace std;
char a[2000001],b[2000001];
int v[2000001],poz[1002],n,m;
void prefix()
{
	int i,q;
	q=0;
	v[1]=0;
	for(i=2;i<=n;i++) {
		while((q)&&(a[i]!=a[q+1]))
			q=v[q];
		if(a[i]==a[q+1])
			q++;
		v[i]=q;
	}
}
int main ()
{
	int i,p,q;
	ifstream f("strmatch.in");
	ofstream g("strmatch.out");
	f>>a>>b;
	f.close();
	n=strlen(a);
	m=strlen(b);
	for(i=n;i>=0;i--)
		a[i]=a[i-1];
	a[0]=' ';
	for(i=m;i>=0;i--)
		b[i]=b[i-1];
	b[0]=' ';
	prefix();
	p=0;
	q=0;
	for(i=1;i<=m;i++) {
		while((q)&&(b[i]!=a[q+1]))
			q=v[q];
		if(b[i]==a[q+1])
			q++;
		if(q==n) {
			q=v[n];
			p++;
			if(p<=1000) 
				poz[p]=i-n;
		}
	}
	g<<p<<'\n';
	if(p>1000)
		p=1000;
	for(i=1;i<=p;i++)
		g<<poz[i]<<" ";
	g.close();
	return 0;
}