Cod sursa(job #1420445)

Utilizator gabi.cristacheGabi Cristache gabi.cristache Data 18 aprilie 2015 15:13:49
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <iostream>
#include <string>
#include <vector>
#include <fstream>

int min(int a, int b) {
	return a < b ? a : b;
}

using namespace std;

int main() {
	string A, B;
	ifstream fin("strmatch.in");
	ofstream fout("strmatch.out");


	fin >> A >> B;

	int M = A.length();
	int N = B.length();

	A = " " + A;
	B = " " + B;

	vector<int> pi(M + 1, 0);
	vector<int> pos(1010, 0);

	int q = 0;
	for (int i = 2; i <= M; ++i) {
		while (q && A[q + 1] != A[i]) {
			q = pi[q];
		}

		if (A[q + 1] == A[i]) {
			++q;
		}

		pi[i] = q;
	}

	q = 0;
	int n = 0;
	for (int i = 1; i <= N; ++i) {
		while (q && A[q + 1] != B[i]) {
			q = pi[q];
		}

		if (A[q + 1] == B[i]) {
			++q;
		}

		if (q == M) {
			q = pi[M];
			
			++n;

			if (n <= 1000) {
				pos[n] = i - M;
			}
		}

	}

	fout << n << '\n';
	for (int i = 1; i <= min(1000, n); ++i) {
		fout << pos[i] << ' ';
	}
	fout << '\n';

	return 0;
}