Cod sursa(job #2081337)

Utilizator flibiaVisanu Cristian flibia Data 4 decembrie 2017 17:09:29
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <bits/stdc++.h>

using namespace std;

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

string a, b; 
int sza, szb, aux[2000100], sol[1010], cnt;

void build(){
	int i = 1, j = 2;
	for(; j <= sza; j++){
		while(a[j] != a[i] && i > 1)
			i = aux[i - 1] + 1;
		if(a[j] == a[i])
			aux[j] = i++;
	}
}

void solve(){
	int i = 1, j = 1;
	for(; j <= szb; j++){
		while(b[j] != a[i] && i > 1)
			i = aux[i - 1] + 1;
		if(i == sza)
			sol[++cnt] = j - i;
		if(b[j] == a[i])
			i++;
		if(cnt > 1000)
			break;
	}
	out << cnt << '\n';
	for(int i = 1; i <= cnt; i++)
		out << sol[i] << ' ';
}

int main(){
	in >> a >> b;
	sza = a.size();
	szb = b.size();
	a = '+' + a;
	b = '+' + b;
	build();
	solve();
	return 0;
}