Pagini recente » Profil Nemultumitu | Cod sursa (job #2331419) | Cod sursa (job #958143) | Cod sursa (job #2758889) | Cod sursa (job #3291636)
#include <fstream>
#include <vector>
#include <string>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const long long mod1 = 666013, mod2 = 666037;
const long long b1 = 109, b2 = 101;
string a, b;
long long h1, h2, hc1, hc2, numi;
vector<long long> aux;
long long expo(long long a, long long b, long long mod)
{
long long ans = 1;
while(b)
if(b % 2 == 0)
b /= 2, a = (1LL * a * a) % mod;
else
b --, ans = (1LL * ans * a) % mod;
return ans;
}
long long get_num(char x){
return x - 'A' + 1;
}
int main()
{
f >> a >> b;
if(b.size() < a.size()){
g << 0;
return 0;
}
for(auto s : a)
{
long long x = get_num(s);
h1 *= b1; h1 += x;
h2 *= b2; h2 += x;
h1 %= mod1; h2 %= mod2;
}
for(long long i = 0; i < a.size(); i ++)
{
long long x = get_num(b[i]);
hc1 = (hc1 * b1) % mod1; hc1 += x;
hc2 = (hc2 * b2) % mod2; hc2 += x;
hc1 %= mod1; hc2 %= mod2;
}
if(hc1 == h1 && hc2 == h2)
numi ++, aux.push_back(0);
for(long long i = a.size(); i < b.size(); i ++)
{
long long x = get_num(b[i]);
hc1 = (hc1 - get_num(b[i - a.size()]) * expo(b1, a.size() - 1, mod1) + mod1) % mod1;
hc1 = (hc1 * b1) % mod1; hc1 += x; hc1 %= mod1;
hc2 = (hc2 - get_num(b[i - a.size()]) * expo(b2, a.size() - 1, mod2) + mod2) % mod2;
hc2 = (hc2 * b2) % mod2; hc2 += x; hc2 %= mod2;
if(hc1 == h1 && hc2 == h2)
numi ++, aux.push_back(i - a.size() + 1);
while(aux.size() > 1000)
aux.pop_back();
}
g << numi << '\n';
for(auto x : aux)
g << x << " ";
return 0;
}