Cod sursa(job #467906)

Utilizator S7012MYPetru Trimbitas S7012MY Data 1 iulie 2010 12:06:56
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <string>
#define DN 2000001
using namespace std;

int pr[DN],m;
string a,b;

void p() {
	int k=0,q;
	m=a.size();
	--m;
	for(q=2; q<=m; q++) {
		while( k && a[k+1]!=a[q])
			k=pr[k];
		if(a[k+1]==a[q]) ++k;
		pr[q]=k;
	}
}
	

int main()
{
	ifstream f("strmatch.in");
	ofstream g("strmatch.out");
	vector<int> sol;
	vector<int>::iterator it;
	string c,d;
	int i,q=0,n,cont=0;
	a=" ",b=" ";
	f>>c;
	f.get();
	f>>d;
	a+=c;
	b+=d;
	n=b.size();
	--n;
	p();
	///<kmp>
	for(i=0; i<n; i++) {
		for( ;q>0 && a[q+1]!=b[i]; q=pr[q]);
		if(a[q+1]==b[i]) ++q;
		if(q==m) {
			++cont;
			sol.push_back(i-m);
		}
	}
	///</kmp>
	g<<cont<<"\n";
	for(it=sol.begin(),i=0;i<=1000 && it!=sol.end(); i++,it++) g<<*it<<" ";
	g<<"\n";
	f.close();
	g.close();
	return 0;
}