Pagini recente » Cod sursa (job #3332747) | Cod sursa (job #3332748) | Cod sursa (job #1710908) | Monitorul de evaluare | Cod sursa (job #826127)
Cod sursa(job #826127)
//
// 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 <cstring>
#define D 73
#define Q 100007
#define MAXN 2000001
int match[MAXN];
char P[MAXN];
char T[MAXN];
int main(void){
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s %s", P, T);
std::cerr << "P: " << P << std::endl;
std::cerr << "T: " << T << std::endl;
// preprocess
int n = strlen(T);
int m = strlen(P);
if(m>n){
std::cout << "0" << std::endl;
return 0;
}
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 hash : " << p << std::endl;
std::cerr << s << " : t hash : " << 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 - (int)T[s]*H) + (int)T[s+m]) % Q;
if (t<0){
t += Q;
}
}
}
std::cout << cnt << std::endl;
for(int i=0;i<cnt;i++){
std::cout << match[i] << " ";
}
std::cout << std::endl;
return 0;
}