Cod sursa(job #963027)

Utilizator andreirulzzzUPB-Hulea-Ionescu-Roman andreirulzzz Data 16 iunie 2013 13:40:09
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <string>
#include <queue>
#include <cstdio>
#include <iostream>
#define NMAX 2000001

int main(){
	std::string A, B;
	std::queue<int> sol;
	int i, k, q, n, m, nr = 0;
	int pi[NMAX];
	
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	
	std::cin >> A >> B;
	n = A.size();
	m = B.size();
	
	for(i = 0; i < n; i++)
		A[i] = toupper(A[i]);
	for(i = 0; i < m; i++)
		B[i] = toupper(B[i]);
	A.insert(0, " ");
	B.insert(0, " ");
	
	k = 0;
	pi[0] = 0;
	for(i = 2; i <= n; i++){
		while(k && A[k + 1] != A[i])
			k = pi[k];
		if (A[k + 1] == A[i])
			++k;
		pi[i] = k;
	}
	
	q = 0;
	for(i = 1; i <= m; i++){
		while(q && A[q + 1] != B[i])
			q = pi[q];
		if (A[q + 1] == B[i])
			++q;
		if (q == n)
			sol.push(i - n), ++nr;
	}
	
	printf("%d\n", nr);
	for(i = 0; i < 1000 && i < nr; i++)
		printf("%d ", sol.front()),sol.pop();
	
	printf("\n"); 
	return 0;
}