Cod sursa(job #1341085)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 12 februarie 2015 13:20:42
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <fstream>
#include <cstring>
#define DIM 2000010
using namespace std;

ifstream fin ("strmatch.in" );
ofstream fout("strmatch.out");

int n, m, i, j, k, ok, minim, l, nr;
char t[DIM]; int p[DIM]; char b[DIM]; int s[DIM];

int main(){
	fin >> t + 1;
	n = strlen(t + 1);
	l = 0;
	for(i = 2; i <= n; i ++){
		while(l != 0 && t[i] != t[l+1])
			l = p[l];
		if(a[i] == a[l+1])
			l ++;
		p[i] = l;
	}
	l = 0;
	fin >> b + 1;
	m = strlen(b + 1);
	for(i = 1; i <= m; i ++){
		while(b[i] != t[l+1] && l != 0)
			l = p[l];
		if(b[i] == t[l+1])
			l ++;
		if(l == n){
			s[++nr] = i - n;
			l = p[l];
		}
	}
	fout << nr << "\n";
	if(nr > 1000)
		nr = 1000;
	for(i = 1; i <= nr; i ++)
		fout << s[i] << " ";

}