Pagini recente » Cod sursa (job #1789198) | Cod sursa (job #2441109) | Monitorul de evaluare | Cod sursa (job #2833234) | Cod sursa (job #2792290)
#include <stdio.h>
#include <vector>
#include <string>
FILE *fin, *fout;
const int DIM = 2e6;
const int P1 = 67;
const int P2 = 61;
const int MOD1 = 1e9 + 7;
const int MOD2 = 1e9 + 9;
int N, M, cnt;
std :: string a(DIM, 0), b(DIM, 0);
std :: vector<int>ans;
int hash_a1, hash_a2, hash_b1, hash_b2;
inline int value(char a) {
if(isupper(a)) {
return a - 'A';
}
if(islower(a)) {
return a - 'a' + 26;
}
if(isdigit(a)) {
return a - '0' + 26 + 26;
}
return 0;
}
int main() {
fin = fopen("strmatch.in", "r");
fout = fopen("strmatch.out", "w");
fscanf(fin, "%s\n%s", const_cast<char*>(a.data()), const_cast<char*>(b.data()));
a = a.data(); b = b.data();
N = a.size();
M = b.size();
if(N > M) {
fprintf(fout, "0\n");
return 0;
}
int p1 = 1, p2 = 1;
for(int i = 0; i < N; i++) {
hash_a1 = ((long long)P1 * hash_a1 % MOD1 + value(a[i])) % MOD1;
hash_a2 = ((long long)P2 * hash_a2 % MOD2 + value(a[i])) % MOD2;
if(i != N - 1) {
p1 = (long long)p1 * P1 % MOD1;
p2 = (long long)p2 * P2 % MOD2;
}
}
for(int i = 0; i < N; i++) {
hash_b1 = ((long long)P1 * hash_b1 % MOD1 + value(b[i])) % MOD1;
hash_b2 = ((long long)P2 * hash_b2 % MOD2 + value(b[i])) % MOD2;
}
if(hash_a1 == hash_b1 && hash_a2 == hash_b2) {
cnt = 1;
ans.push_back(0);
}
// printf("%d %d\n", p1, p2);
for(int i = N; i < M; i++) {
// printf("%d %d\n", hash_b1, hash_b2);
hash_b1 = ((long long)hash_b1 - (long long)value(b[i - N]) * p1 % MOD1 + MOD1) % MOD1;
hash_b2 = ((long long)hash_b2 - (long long)value(b[i - N]) * p2 % MOD2 + MOD2) % MOD2;
hash_b1 = ((long long)hash_b1 * P1 % MOD1 + value(b[i])) % MOD1;
hash_b2 = ((long long)hash_b2 * P2 % MOD2 + value(b[i])) % MOD2;
if(hash_a1 == hash_b1 && hash_a2 == hash_b2) {
if(++cnt <= 1000) {
ans.push_back(i - N + 1);
}
}
}
fprintf(fout, "%d\n", cnt);
for(int i = 0; i < ans.size(); i++) {
fprintf(fout, "%d ", ans[i]);
}
fclose(fin);
fclose(fout);
return 0;
}