Cod sursa(job #927113)

Utilizator andreifirstCioara Andrei Ioan andreifirst Data 25 martie 2013 16:27:31
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <fstream>
#include <string>
using namespace std;

ifstream f("strmatch.in"); ofstream g("strmatch.out");

int i, j, n, m, t, l;
int matchTo;
int r[1005];
string a, b;
int pi[2000005];

int main(){
	f>>b>>a;
	n = a.length();
	m = b.length();
	
	matchTo=0;
	for (i=1; i<m; i++){
		while (matchTo && b[matchTo]!=b[i])	matchTo=pi[matchTo-1];
		if (b[i] == b[matchTo]) pi[i]=++matchTo; 
	}
	
	matchTo=0;
	for (i=0; i<n; i++){
		while (matchTo && b[matchTo]!=a[i]) matchTo = pi[matchTo-1];
		if (a[i] == b[matchTo]) matchTo++;
		if (matchTo==m){
			t++;
			if (t<=1000) r[t] = i-matchTo+1;
		}
	}
	
	g<<t<<"\n";
	for (i=1; i<=t && i<=1000; i++){
		g<<r[i]<<" ";
	}
}