Pagini recente » Cod sursa (job #1795289) | Cod sursa (job #319371) | Cod sursa (job #2704325) | Cod sursa (job #2987242) | Cod sursa (job #3209388)
#include <bits/stdc++.h>
#define NMAX 2000001
#define MAXCOUNT 1000
#define P 73
#define MOD1 100007
#define MOD2 100021
char A[NMAX];
char B[NMAX];
char match[NMAX];
int main()
{
int nr = 0;
int lenA, lenB;
int P1, P2;
int hashA1, hashA2;
int hashB1, hashB2;
std::ifstream fin("strmatch.in");
std::ofstream fout("strmatch.out");
fin >> A >> B;
fin.close();
lenA = strlen(A);
lenB = strlen(B);
if (lenA > lenB) {
fout << nr << '\n';
fout.close();
}
for (int i = 0; i < lenA; ++i) {
hashA1 = (hashA1 * P + A[i]) % MOD1;
hashA2 = (hashA2 * P + A[i]) % MOD2;
if (i > 0) {
P1 = (P1 * P) % MOD1;
P2 = (P2 * P) % MOD2;
}
}
for (int i = 0; i < lenA; ++i) {
hashB1 = (hashB1 * P + B[i]) % MOD1;
hashB2 = (hashB2 * P + B[i]) % MOD2;
}
if (hashA1 == hashB1 && hashA2 == hashB2) {
match[0] = 1;
++nr;
}
for (int i = lenA; i < lenB; ++i) {
hashB1 = ((hashB1 - (B[i - lenA] * P1) % MOD1 + MOD1) * P + B[i]) % MOD1;
hashB2 = ((hashB2 - (B[i - lenA] * P2) % MOD2 + MOD2) * P + B[i]) % MOD2;
if (hashA1 == hashB1 && hashA2 == hashB2) {
match[i - lenA + 1] = 1;
++nr;
}
}
fout << nr << '\n';
nr = 0;
for (int i = 0; i < lenB && nr < MAXCOUNT; ++i)
if (match[i]) {
++nr;
fout << i << ' ';
}
fout << '\n';
fout.close();
return 0;
}