Pagini recente » Cod sursa (job #368832) | Cod sursa (job #2979299) | Cod sursa (job #2407101) | Cod sursa (job #2478574) | Cod sursa (job #3195175)
#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#define int long long
long long Mod = 1000000007;
long long P = 1007;
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;
signed 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;
}
signed cnt = 0;
vector<signed> 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, 1000); i++) fout << poz[i] << " ";
fout << '\n';
return 0;
}