Pagini recente » Cod sursa (job #1205767) | Cod sursa (job #1144914) | Cod sursa (job #1490042) | Cod sursa (job #1217799) | Cod sursa (job #825146)
Cod sursa(job #825146)
//
// 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 <vector>
#define D 92
#define Q 100001
int main(void){
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
std::vector<int> match;
std::string P;
std::string T;
std::cin >> P;
std::cin >> T;
// preprocess
int n = T.length();
int m = P.length();
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 : " << p << " : t : " << t << std::endl;
if ( p == t ) {
if(P.compare(0,m,T,s,m)==0){
// std::cerr << "match found at " << s << std::endl;
cnt++;
match.push_back(s);
}
}
if ( s < n-m ) {
t = (D*(t - T[s]*H) + T[s+m]) % Q;
if (t<0){
t += Q;
}
}
}
std::cout << cnt << std::endl;
for(std::vector<int>::const_iterator it=match.begin(); it != match.end(); it++){
std::cout << (*it) << " ";
}
std::cout << std::endl;
}