Pagini recente » Cod sursa (job #1631573) | Cod sursa (job #373782) | Cod sursa (job #2776047) | Cod sursa (job #934172) | Cod sursa (job #3195165)
#include <bits/stdc++.h>
long long Mod = 1000000007;
long long P = 1007;
#define int long long
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
string a, b; fin >> a >> b;
int n = a.size(), m = b.size();
//cout << "n = " << n << " m = " << m << endl;
int pw[m];
pw[0] = 1;
for(int i = 1; i < m; i++){
pw[i] = (pw[i - 1] * P) % Mod;
}
int hasha = 0;
for(int i = 0; i < n; i++){
hasha = (hasha + a[i] * pw[i]) % Mod;
}
int hashb[m];
hashb[0] = b[0];
for(int i = 0; i < m; i++){
hashb[i] = (hashb[i - 1] + b[i] * pw[i]) % Mod;
}
int cnt = 0;
vector<int> poz;
for(int i = 0; i <= m - n; i++){
int ch = 0;
if(i == 0) ch = hashb[n - 1];
else ch = (hashb[i + n - 1] - hashb[i - 1] + Mod) % Mod;
//cout << "i = " << i << " ch = " << ch << " hasha = " << hasha << endl;
if(ch == (hasha * pw[i]) % Mod){
cnt++;
poz.push_back(i);
}
}
fout << cnt << '\n';
for(int i = 0; i < min(cnt, 1000ll); i++) fout << poz[i] << " ";
fout << '\n';
return 0;
}