Cod sursa(job #933661)

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

#define NMAX 2000002

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

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

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