Cod sursa(job #825146)

Utilizator radu.bRadu Brumariu radu.b Data 27 noiembrie 2012 17:07:21
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
//
//  005.2.cpp
//  005.1
//
//  Created by Radu Brumariu on 11/22/12.
//  Copyright (c) 2012 Radu Brumariu. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>

#define D 92
#define Q 100001

int main(void){
	
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	std::vector<int> match;
	
	std::string P;
	std::string T;
	
	std::cin >> P;
	std::cin >> T;
	
	// preprocess
	
	int n = T.length();
	int m = P.length();
	
	int H = (int)(pow(D,m-1)) % Q;
	
	int p = 0;
	int t = 0;
	
	
	// preprocessing
	for (int i = 0; i < m; i++) {
		p = (D*p + P[i]) % Q;
		t = (D*t + T[i]) % Q;
	}
	
	// match
	int cnt = 0;
	for (int s = 0; s < n-m; s++) {
//		std::cerr << s << " : p : " << p << " : t : " << t << std::endl;
		if ( p == t ) {
			if(P.compare(0,m,T,s,m)==0){
//				std::cerr << "match found at " << s << std::endl;
				cnt++;
				match.push_back(s);
			}
		}
		if ( s < n-m ) {
			t = (D*(t - T[s]*H) + T[s+m]) % Q;
			if (t<0){
				t += Q;
			}
		}
	}
	
	std::cout << cnt << std::endl;
	for(std::vector<int>::const_iterator it=match.begin(); it != match.end(); it++){
		std::cout << (*it) << " ";
	}
	std::cout << std::endl;
	
}