Cod sursa(job #826129)

Utilizator radu.bRadu Brumariu radu.b Data 30 noiembrie 2012 04:38:31
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 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 Q1 1000003
#define Q2 1000033
#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);

	int n = strnlen(T, MAXN);
	int m = strnlen(P, MAXN);
	
	if(m>n){
		std::cout << "0" << std::endl;
		return 0;
	}
	
	int H1 = 1, H2 = 1;
	int p1 = 0, p2 = 0;
	int t1 = 0, t2 = 0;
	
	// preprocessing
	for (int i = 0; i < m; i++) {
		p1 = (D * p1 + P[i]) % Q1;
		p2 = (D * p2 + P[i]) % Q2;
		t1 = (D * t1 + T[i]) % Q1;
		t2 = (D * t2 + T[i]) % Q2;
		if(i!=0){
			H1 = (H1*D) % Q1;
			H2 = (H2*D) % Q2;
		}

	}
	
	// match
	int cnt = 0;
	for (int s = 0; s < n-m; s++) {
		if ( p1 == t1 && p2 == t2 ) {
				match[cnt++]=s;
		}
		t1 = (D*((t1 - T[s]*H1)%Q1 + Q1) + T[s+m]) % Q1;
		t2 = (D*((t2 - T[s]*H2)%Q2 + Q2) + T[s+m]) % Q2;
	}
	
	std::cout << cnt << std::endl;
	for(int i=0;i<cnt;i++){
		std::cout << match[i] << " ";
	}
	std::cout << std::endl;
	return 0;
}