Pagini recente » Diferente pentru problema/papuci intre reviziile 7 si 6 | Cod sursa (job #1308490) | Cod sursa (job #1308487) | Cod sursa (job #826130) | Cod sursa (job #826128)
Cod sursa(job #826128)
//
// 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;
}