Pagini recente » Monitorul de evaluare | Cod sursa (job #1716846) | Cod sursa (job #132291) | Cod sursa (job #1084448) | Cod sursa (job #1976883)
#include <bits/stdc++.h>
using namespace std;
#define NMAX 2000002
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char A[NMAX], B[NMAX];
unsigned long long Bpow[NMAX];
const int BASE = 29;
unsigned long long hashUp(const int N) {
unsigned long long h = 0;
Bpow[0] = 1;
for (int i = 0; i < N; ++i) {
Bpow[i + 1] = Bpow[i] * BASE;
h = h * BASE + A[i];
}
return h;
}
int main() {
fin >> A >> B;
int N = strlen(A);
int M = strlen(B);
unsigned long long hashA = hashUp(N);
int nrMatches = 0;
vector<int> poz;
unsigned long long hashB = 0;
for (int i = 0; i < M; ++i) {
hashB = hashB * BASE + B[i];
if (i >= N)
hashB -= Bpow[N] * B[i - N];
if (i >= N - 1 && hashB == hashA) {
nrMatches++;
if (nrMatches <= 1000)
poz.push_back(i - N + 1);
}
}
fout << nrMatches << "\n";
for (auto val: poz)
fout << val << " ";
return 0;
}