Pagini recente » Cod sursa (job #972010) | Cod sursa (job #2061368) | Clasament Teme ACM Unibuc 2013 | Cod sursa (job #1268351) | Cod sursa (job #2085042)
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
inline void debugMode() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
#endif // ONLINE_JUDGE
}
inline void PrintYes() { cout << "Yes"; }
inline void PrintNo() { cout << "No"; }
const double eps = 1e-7;
const int Nmax = 2e6 + 1;
const int prime_number = 101;
vector< int > ind;
void Rabin_Karp(string pat, string txt)
{
int h = 1;
int N, M;
M = (int)pat.size();
N = (int)txt.size();
///h = 256^(M-1)
for(int i = 0; i < M - 1; ++i)
h = (h * 256) % prime_number;
int hash_pat = 0; /// hash value pentru pattern
int hash_txt = 0; /// hash value pentru text
/// hash value pentru pattern si respectiv pria subsecventa din text
for(int i = 0; i < M; ++i) {
hash_pat = (256 * hash_pat + pat[i]) % prime_number;
hash_txt = (256 * hash_txt + txt[i]) % prime_number;
}
int j;
for(int i = 0; i <= N - M; ++i) {
/// daca au aceeasi valoare a hash-urilor
if(hash_pat == hash_txt) {
for(j = 0; j < M; ++j) /// verific sa fie intr-adevar acelasi string
if(txt[i + j] != pat[j]) /// inseamnca nu sunt la fel si nu mai continui
break;
if(j == M) /// verific daca sunt aceleasi string-uri
ind.push_back(i);
}
/// recalculez urmatoarea valoare a hash-ului pentru stringul txt[i+1...i+M]
if(i < N - M) {
hash_txt = (256 * (hash_txt - txt[i] * h) + txt[i + M]) % prime_number;
if(hash_txt < 0)
hash_txt += prime_number;
}
}
}
int main()
{
debugMode();
string pat, txt;
cin >> pat >> txt;
Rabin_Karp(pat, txt);
cout << ind.size() << '\n';
for(auto it: ind)
cout << it << " ";
return 0;
}