Cod sursa(job #991931)

Utilizator cont_de_testeCont Teste cont_de_teste Data 31 august 2013 20:36:38
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

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

const int MAX = 2000100;

char a[MAX], b[MAX];
int l1, l2, q;

int sol, soln[1010];

int pi[MAX];


int main() {
	fin.getline(a + 1, MAX - 1);
	fin.getline(b + 1, MAX - 1);
	
	l1 = strlen(a + 1);
	l2 = strlen(b + 1);
	
	q = 0;
	for (int i = 2; i <= l1; ++i) {
		while (q > 0 && a[i] != a[q + 1])
			q = pi[q];
		if (a[i] == a[q + 1])
			++q;
		pi[i] = q;
	}
	
	q = 0;
	for (int i = 1; i <= l2; ++i) {
		while (q > 0 && b[i] != a[q + 1])
			q = pi[q];
		if (b[i] == a[q + 1])
			++q;
		if (q == l1) {
			++sol;
			if (sol <= 1000) {
				soln[sol] = i - l1 + 1;
			}
			q = pi[q];
		}
	}
	
	fout << sol << '\n';
	for (int i = 1; i <= sol; ++i)
		fout << soln[i] - 1 << ' ';
}