Pagini recente » Cod sursa (job #2623027) | Cod sursa (job #379986) | Cod sursa (job #1379906) | Cod sursa (job #230127) | Cod sursa (job #1134260)
#include <iostream>
#include <string>
#include <fstream>
#include <stdio.h>
using namespace std;
const int P = 101;
const int MOD1 = 31627;
const int MOD2 = 31013;
int match[1005];
int main()
{
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
string A, B;
getline(f, A);
getline(f, B);
int NA = A.size(), NB = B.size();
int hash1 = 0, hash2 = 0, P1 = 1, P2 = 1;
for (int i = 0; i < NA; i++)
{
hash1 = (hash1 * P + A[i]) % MOD1;
hash2 = (hash2 * P + A[i]) % MOD2;
P1 = (P1 * P) % MOD1;
P2 = (P2 * P) % MOD2;
}
if (NA > NB) {
g << 0 << endl;
return 0;
}
int H1 = 0, H2 = 0;
for (int i = 0; i < NA; i++) {
H1 = (H1 *P + B[i]) % MOD1;
H2 = (H2 *P + B[i]) % MOD2;
}
int cnt = 0;
if (hash1 == H1 && hash2 == H2) {
cnt++; match[0] = 0;
}
for (int i = NA; i < NB; i++) {
H1 = (H1*P + B[i] - P1*B[i-NA]) % MOD1;
if (H1 < 0) H1 += MOD1;
H2 = (H2*P + B[i] - P2*B[i-NA]) % MOD2;
if (H2 < 0) H2 += MOD2;
if (hash1 == H1 && hash2 == H2) {
if (cnt < 1000) match[cnt] = i-NA+1;
cnt++;
}
}
g << cnt << '\n';
for (int i = 0; i < 1000 && i < cnt; i++)
g << match[i] << ' ';
g << endl;
return 0;
}