Pagini recente » Cod sursa (job #1148588) | Cod sursa (job #211019) | Cod sursa (job #553140) | Cod sursa (job #3169985) | Cod sursa (job #2910359)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b;
const int p = 53;
const int m = 1e9 + 9;
int main(){
fin >> a >> b;
int A = a.size(), B = b.size();
vector<long long> p_pow(max(A, B) + 1);
p_pow[0] = 1;
for(int i = 1; i < (int) p_pow.size(); i++)
p_pow[i] = (p_pow[i - 1] * p) % m;
vector<long long> h(B + 1, 0);
for(int i = 0; i < B; i++)
h[i + 1] = (h[i] + (b[i] - 'A' + 1) * p_pow[i]) % m;
long long h_a = 0;
for(int i = 0; i < A; i++)
h_a = (h_a + (a[i] - 'A' + 1) * p_pow[i]) % m;
vector<int> occurences;
for(int i = 0; i + A - 1 < B; i++){
long long cur_h = (h[i + A] + m - h[i]) % m;
if(cur_h == h_a * p_pow[i] % m)
occurences.push_back(i);
}
fout << occurences.size() << '\n';
for(int i = 0; i < min(1000, (int) occurences.size()); i++)
fout << occurences[i] << ' ';
}