Cod sursa(job #1226784)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 7 septembrie 2014 15:34:19
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>
#include <cstring>
#define DIM 2000005

using namespace std;

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

char A[DIM], B[DIM], C[DIM];

int Pi[DIM];

int sol, Sol[DIM];

int main() {
	fin >> B;
	fin >> A;
	int n = strlen(A);
	int m = strlen(B);
	strcpy(C, B);
	strcpy(B + 1, C);
	strcpy(C, A);
	strcpy(A + 1, C);
	for (int i = 2; i <= m; ++i) {
		int q = Pi[i - 1];
		while (q && B[i] != B[q + 1])
			q = Pi[q];
		if (B[i] == B[q + 1])
			Pi[i] = q + 1;
	}
	int q = 0;
	for (int i = 1; i <= n; ++i) {
		while (q && A[i] != B[q + 1])
			q = Pi[q];
		if (A[i] == B[q + 1])
			q++;
		if (q == m) {
			++sol;
			Sol[sol] = i - m;
			q = Pi[q];
		}
	}
	fout << sol << "\n";
	for (int i = 1; i <= sol && i <= 1000; ++i)
		fout << Sol[i] << " ";
	return 0;
}