Pagini recente » Cod sursa (job #2721884) | Cod sursa (job #2874846) | Cod sursa (job #592029) | Cod sursa (job #2874649) | Cod sursa (job #1292716)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream in ("strmatch.in");
ofstream out ("strmatch.out");
const int MAXN = 2000001;
const int P = 73;
const int MOD1 = 666013;
const int MOD2 = 666773;
char A[MAXN], B[MAXN];
bool Match[MAXN];
int main()
{
int N, M, i;
int hashA1 = 0, hashA2 = 0;
int hash1 = 0, hash2 = 0;
int P1 = 1, P2 = 1;
int Ans = 0;
in >> A;
N = strlen (A);
in >> B;
M = strlen (B);
if (N > M){
out << "0";
return 0;
}
for (i = 0; i < N; i ++){
hashA1 = (hashA1 * P + A[i]) % MOD1;
hashA2 = (hashA2 * P + A[i]) % MOD2;
if (i){
P1 = (P1 * P) % MOD1;
P2 = (P2 * P) % MOD2;
}
}
for (i = 0; i < N; i ++){
hash1 = (hash1 * P + B[i]) % MOD1;
hash2 = (hash2 * P + B[i]) % MOD2;
}
if (hash1 == hashA1 && hash2 == hashA2){
Match[0] = 1;
Ans ++;
}
for (i = N; i < M; i ++){
hash1 = (((hash1 - (B[i - N] * P1)) % MOD1 + MOD1) * P + B[i]) % MOD1;
hash2 = (((hash2 - (B[i - N] * P2)) % MOD2 + MOD2) * P + B[i]) % MOD2;
if (hash1 == hashA1 && hash2 == hashA2){
Ans ++;
Match[i - N + 1] = 1;
}
}
out << Ans << "\n";
Ans = 0;
for (i = 0; i < M && Ans < 1000; i ++)
if (Match[i]){
out << i << " ";
Ans ++;
}
return 0;
}