Pagini recente » Cod sursa (job #544092) | Cod sursa (job #1381285) | Cod sursa (job #836693) | Cod sursa (job #392206) | Cod sursa (job #3256056)
#include <fstream>
#define int long long
using namespace std;
const int B = 127, Mod = 1e9 + 7, Lmax = 2e6 + 5;
int inv[Lmax], ans[Lmax], p[Lmax];
int pow(int a, int b)
{
if(b == 0) return 1;
if(b == 1) return a;
int aux = pow(a, b / 2);
if(b % 2 == 0)
return aux * aux % Mod;
return ((aux * aux) % Mod) * a % Mod;
}
int invmod(int a)
{
return pow(a, Mod - 2);
}
signed main()
{
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int n, m, i, hasha = 0, hashb = 0, poz = 0;
string a, b;
cin >> a >> b;
n = a.size(); m = b.size();
for(i = 0; i < n; i ++) {
p[i] = pow(B, i);
hasha = (hasha + ((a[i] - '0' + 1) * p[i] % Mod)) % Mod;
}
for(int i = 0; i < n; i++) {
hashb = (hashb + ((b[i] - '0' + 1) * p[i] % Mod)) % Mod;
}
if(hashb == hasha) {
ans[++poz] = 0;
}
int invB = invmod(B);
int pB = pow(B, n - 1);
for(i = n; i < m; i++)
{
hashb = (hashb - (b[i - n] - '0' + 1) + Mod) % Mod;
hashb = (hashb * invB);
hashb = (hashb + ((b[i] - '0' + 1) * pB % Mod)) % Mod;
if(hashb == hasha) {
ans[++poz] = i - n + 1;
}
}
cout << poz << '\n';
for(i = 1; i <= min(poz, 1LL * 1000); i ++)
cout << ans[i] << " ";
return 0;
}