Pagini recente » Cod sursa (job #1508332) | Cod sursa (job #979506) | Cod sursa (job #671096) | Cod sursa (job #2982477) | Cod sursa (job #2420496)
#include <stdio.h>
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define repa(i, l, r) for (int i = l; i < r; i++)
#define repd(i, r, l) for (int i = r; i > l; i--)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int P = 73;
const int mod1 = 100007;
const int mod2 = 100021;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
string A, B;
int main(void) {
fin >> A >> B;
int N = A.length();
int M = B.length();
if (M < N) {
fout << 0 << endl;
return 0;
}
int count = 0;
int P1 = 1; // P^(N-1) % mod1
int P2 = 1; // P^(N-1) % mod2
int ah1 = 0; // hash1 of A
int ah2 = 0; // hash2 of A
int bh1 = 0; // Rolling hash1 of B
int bh2 = 0; // Rolling hash2 of B
for(int i = 0; i < N; ++i) {
ah1 = (ah1 * P + A[i]) % mod1;
ah2 = (ah2 * P + A[i]) % mod2;
bh1 = (bh1 * P + B[i]) % mod1;
bh2 = (bh2 * P + B[i]) % mod2;
if (i) {
P1 = (P1 * P) % mod1;
P2 = (P2 * P) % mod2;
}
}
vi res;
if (bh1 == ah1 && bh2 == ah2) {
res.push_back(0);
count++;
}
for(int i = N; i < M; i++) {
bh1 = ((bh1 - (B[i-N]*P1) % mod1 + mod1) * P + B[i]) % mod1;
bh2 = ((bh2 - (B[i-N]*P2) % mod2 + mod2) * P + B[i]) % mod2;
if (bh1 == ah1 && bh2 == ah2) {
if (count < 1000)
res.push_back(i-N+1);
count++;
}
}
fout << count << endl;
for(int pos: res)
fout << pos << ' ';
fout << endl;
return 0;
}