Cod sursa(job #826128)

Utilizator radu.bRadu Brumariu radu.b Data 30 noiembrie 2012 04:20:38
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 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 <cstring>

#define D 73
#define Q 100007
#define MAXN 2000001

int match[MAXN];
char P[MAXN];
char T[MAXN];


int main(void){
		
	(void)freopen("strmatch.in", "r", stdin);
	(void)freopen("strmatch.out", "w", stdout);
	
	scanf("%s %s", P, T);
	
	std::cerr << "P: " << P << std::endl;
	std::cerr << "T: " << T << std::endl;
	
	int n = strnlen(T, MAXN);
	int m = strnlen(P, MAXN);
	
	if(m>n){
		std::cout << "0" << std::endl;
		return 0;
	}
	
	int H = 1;
	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;
		if(i!=0){
			H = (H*D) % Q;
		}

	}
	
	// match
	int cnt = 0;
	for (int s = 0; s < n-m; s++) {
		std::cerr << s << " hash diff " << p - t << std::endl;

		if ( p == t ) {
			std::cerr <<"match at " << s << std::endl;
			if(strncmp(P, T+s, m)==0){
				match[cnt++]=s;
			}
		}
		if ( s < n-m ) {
			t = (D*((t - T[s]*H)%Q + Q) + T[s+m]) % Q;
		}
	}
	
	std::cout << cnt << std::endl;
	for(int i=0;i<cnt;i++){
		std::cout << match[i] << " ";
	}
	std::cout << std::endl;
	return 0;
}