Cod sursa(job #927087)

Utilizator andreifirstCioara Andrei Ioan andreifirst Data 25 martie 2013 16:12:42
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, l, t;
int r[1005];
string a, b;
int pa[2000005];

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