Pagini recente » Monitorul de evaluare | Diferente pentru problema/papuci intre reviziile 7 si 6 | Cod sursa (job #1308490) | Cod sursa (job #1308487) | Cod sursa (job #826130)
Cod sursa(job #826130)
//
// 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+1; 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 < 1000 ;i++){
std::cout << match[i] << " ";
}
std::cout << std::endl;
return 0;
}