Pagini recente » Borderou de evaluare (job #202271) | Cod sursa (job #2773642) | Cod sursa (job #1786378) | Cod sursa (job #2908611) | Cod sursa (job #3171125)
#include <fstream>
#include <string>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
const int MAXN = 2000001;
const int BASE = 73;
const int MOD1 = 100007;
const int MOD2 = 100021;
string str, templ;
int N, M;
int hash1, hash2, pow1, pow2;
char match[MAXN];
int main() {
cin >> str >> templ;
N = str.size();
M = templ.size();
pow1 = pow2 = 1;
hash1 = hash2 = 0;
for (int i = 0; i < N; i++) {
hash1 = (hash1 * BASE + str[i]) % MOD1;
hash2 = (hash2 * BASE + str[i]) % MOD2;
if (i != 0)
pow1 = (pow1 * BASE) % MOD1,
pow2 = (pow2 * BASE) % MOD2;
}
if (N > M) {
cout << "0\n";
return 0;
}
int hash1_clone = 0, hash2_clone = 0;
for (int i = 0; i < N; i++){
hash1_clone = (hash1_clone * BASE + templ[i]) % MOD1,
hash2_clone = (hash2_clone * BASE + templ[i]) % MOD2;
}
int Nr = 0;
if (hash1_clone == hash1 && hash2_clone == hash2)
match[0] = 1, Nr++;
for (int i = N; i < M; i++) {
hash1_clone = ((hash1_clone - (templ[i - N] * pow1) % MOD1 + MOD1) * BASE + templ[i]) % MOD1;
hash2_clone = ((hash2_clone - (templ[i - N] * pow2) % MOD2 + MOD2) * BASE + templ[i]) % MOD2;
if (hash1_clone == hash1 && hash2_clone == hash2){
match[i - N + 1] = 1;
Nr++;
}
}
cout << Nr << '\n';
Nr = 0;
for (int i = 0; i < N && Nr < 1000; i++){
if (match[i]){
Nr++;
cout << i << ' ';
}
}
cout << '\n';
return 0;
}