Pagini recente » Cod sursa (job #2000509) | Cod sursa (job #86527) | Cod sursa (job #781775) | Cod sursa (job #1696457) | Cod sursa (job #2353136)
#include <cstring>
#include <fstream>
#define BASE 73
#define MOD1 100007
#define MOD2 666013
#define MAX 1000
#define SMAX 2000010
std::ifstream fin("strmatch.in");
std::ofstream fout("strmatch.out");
int m; char a[SMAX];
int n; char b[SMAX];
int nrSol;
int sol[SMAX];
int main() {
fin >> a; m = strlen(a);
fin >> b; n = strlen(b);
int hash01 = 0, hash1 = 0, power1 = 1;
int hash02 = 0, hash2 = 0, power2 = 1;
for (int i = 0; i < m; i++) {
hash01 = (hash01 * BASE + a[i] - 'A' + 1) % MOD1;
hash02 = (hash02 * BASE + a[i] - 'A' + 1) % MOD2;
hash1 = (hash1 * BASE + b[i] - 'A' + 1) % MOD1;
hash2 = (hash2 * BASE + b[i] - 'A' + 1) % MOD2;
}
for (int i = 1; i < m; i++) {
power1 = power1 * BASE % MOD1;
power2 = power2 * BASE % MOD2;
}
if (hash1 == hash01 && hash2 == hash02)
sol[nrSol++] = 0;
for (int i = m; i < n; i++) {
hash1 = ((hash1 - (b[i - m] - 'A' + 1) * power1 % MOD1 + MOD1) * BASE + b[i] - 'A' + 1) % MOD1;
hash2 = ((hash2 - (b[i - m] - 'A' + 1) * power2 % MOD2 + MOD2) * BASE + b[i] - 'A' + 1) % MOD2;
if (hash1 == hash01 && hash2 == hash02)
sol[nrSol++] = i - m + 1;
}
fout << nrSol << '\n';
for (int i = 0; i < nrSol && i < MAX; i++)
fout << sol[i] << ' ';
fout << '\n';
fout.close();
return 0;
}