Pagini recente » Cod sursa (job #1125161) | Cod sursa (job #844672) | Cod sursa (job #2177040) | Cod sursa (job #1262997) | Cod sursa (job #2985044)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMAX = 2000000;
const int MOD = 1e9 + 7; //
const int BASE = 29;
int n, m;
char A[NMAX + 1], B[NMAX + 1];
int powBASE[NMAX + 1];
int nr, v[1001];
int hA, hB;
// n n-1 0
// [------------]
// [------------]
// n n-1 0
int main() {
fin >> A >> B;
n = strlen(A);
m = strlen(B);
if(n > m) {
fout << "0\n";
return 0;
}
powBASE[0] = 1;
for(int i = 1; i <= n; i++) {
powBASE[i] = (long long) powBASE[i - 1] * BASE % MOD;
}
for(int i = 0; i < n; i++) {
hA = (long long) hA * BASE % MOD + (A[i] - 'A');
if(hA >= MOD) {
hA -= MOD;
}
}
for(int i = 0; i < n; i++) {
hB = (long long) hB * BASE % MOD + (B[i] - 'A');
if(hB >= MOD) {
hB -= MOD;
}
}
if(hA == hB) {
nr++;
v[nr] = 0;
}
for(int i = 1; i + n - 1 < m; i++) {
hB -= (long long) (B[i - 1] - 'A') * powBASE[n - 1] % MOD;
if(hB < 0) {
hB += MOD;
}
hB = (long long) hB * BASE % MOD;
hB += (B[i + n - 1] - 'A');
if(hB >= MOD) {
hB -= MOD;
}
if(hA == hB) {
nr++;
if(nr <= 1000) {
v[nr] = i;
}
}
}
fout << nr << '\n';
for(int i = 1; i <= min(nr, 1000); i++) {
fout << v[i] << " ";
}
return 0;
}