Pagini recente » Borderou de evaluare (job #2456646) | Cod sursa (job #1406127) | Cod sursa (job #3263901) | Cod sursa (job #1393210) | Cod sursa (job #2809761)
#include<bits/stdc++.h>
using namespace std;
char A[2000005], B[2000005];
long long N, P[1005];
struct Hash
{
long long base, modulo, power, value;
Hash(int b, int m) { base = b, modulo = m, power = 0, value = 0; }
void init(char* S, int length)
{
power = 1, value = 0;
for (int i = length - 1; i >= 0; --i)
{
value = (value + (1LL * power * S[i]) % modulo) % modulo;
if (i) power = (power * base) % modulo;
}
}
void roll(char toRemove, char toAdd)
{ value = (((value - (1LL * toRemove * power) % modulo + modulo) * base) % modulo + toAdd) % modulo; }
bool operator==(const Hash& other) const
{ return value == other.value; }
};
int main()
{
cin >> A >> B;
int length_A = strlen(A);
int length_B = strlen(B);
Hash hash_A1{ 257, (int)2e9 + 7 }, hash_B1{ 257, (int)2e9 + 7 };
Hash hash_A2{ 263, (int)2e9 + 9 }, hash_B2{ 263, (int)2e9 + 9 };
hash_A1.init(A, length_A); hash_B1.init(B, length_A);
hash_A2.init(A, length_A); hash_B2.init(B, length_A);
if (hash_A1.value == hash_B1.value && hash_A2.value == hash_B2.value)
++N;
for (int i = length_A; i < length_B; ++i)
{
hash_B1.roll(B[i - length_A], B[i]);
hash_B2.roll(B[i - length_A], B[i]);
if (hash_A1.value == hash_B1.value && hash_A2.value == hash_B2.value)
{
if (N <= 1000) P[++N] = i - length_A + 1;
else ++N;
}
}
cout << N << '\n';
if (N > 1000) N = 1000;
for (int i = 1; i <= N; ++i) cout << P[i] << ' ';
return 0;
}