Cod sursa(job #902969)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 1 martie 2013 17:46:55
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include<iostream>
#include<fstream>
#include<string.h>
using namespace std;

#define NMAX 2000002
#define PMAX 1001

char a[NMAX],b[NMAX];
int v[NMAX],p[PMAX];

inline void prefix(int n)
{
	int i,q;
	v[1]=0;
	q=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,j,nr,n,m,q;
	ifstream f("strmatch.in");
	ofstream g("strmatch.out");
	f>>(a+1)>>(b+1);
	n=strlen(a+1);
	m=strlen(b+1);
	a[0]=' ';
	b[0]=' ';
	prefix(n);
	nr=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];
			nr++;
			if(nr<=PMAX-1)
				p[nr]=i-n;
		}
	}
	g<<nr<<'\n';
	if(nr>1000)
		nr=1000;
	for(i=1;i<=nr;i++)
		g<<p[i]<<" ";
	g.close();
	return 0;
}