Pagini recente » Cod sursa (job #1468228) | Cod sursa (job #3272321) | Cod sursa (job #613333) | Cod sursa (job #630307) | Cod sursa (job #3256061)
#include <fstream>
#define int long long
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
const int B = 127, Mod = 1e9 + 7;
int ans[2000005];
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()
{
int n, m, i, hasha = 0, hashb = 0, poz = 0, putere, inv;
string a, b;
cin >> a >> b;
n = a.size(); m = b.size();
for(i = 0; i < n; i ++)
hasha = (hasha + ((a[i] - '0' + 1) * pow(B, i) % Mod)) % Mod;
for(int i = 0; i < n; i++)
hashb = (hashb + ((b[i] - '0' + 1) * pow(B, i) % Mod)) % Mod;
if(hashb == hasha)
ans[++poz] = 0;
putere = pow(B, n - 1);
inv = invmod(B);
for(i = n; i < m; i++)
{
hashb = (hashb - (b[i - n] - '0' + 1) + Mod) % Mod;
hashb = (hashb * inv) % Mod;
hashb = (hashb + ((b[i] - '0' + 1) * putere % 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;
}