Pagini recente » Cod sursa (job #1516295) | Cod sursa (job #478806) | Cod sursa (job #725473) | Cod sursa (job #823534) | Cod sursa (job #3291659)
#include <fstream>
#include <vector>
#include <string>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int mod1 = 666013, mod2 = 666037;
const int bz = 109;
string a, b;
int h1, h2, hc1, hc2, numi;
vector<int> aux;
int expo(int a, int b, int mod)
{
int ans = 1;
while(b)
if(b % 2 == 0)
b /= 2, a = (1LL * a * a) % mod;
else
b --, ans = (1LL * ans * a) % mod;
return ans;
}
int get_num(char x){
return x - 'A' + 1;
}
int main()
{
f >> a >> b;
if(b.size() < a.size()){
g << 0;
return 0;
}
int p = 1;
for(auto s : a)
{
int x = get_num(s);
h1 *= bz; h1 += x;
h2 *= bz; h2 += x;
h1 %= mod1; h2 %= mod2;
p *= bz;
}
p /= bz;
for(int i = 0; i < a.size(); i ++)
{
int x = get_num(b[i]);
hc1 *= bz; hc1 += x;
hc2 *= bz; hc2 += x;
hc1 %= mod1; hc2 %= mod2;
}
if(hc1 == h1 && hc2 == h2)
numi ++, aux.push_back(0);
for(int i = a.size(); i < b.size(); i ++)
{
int x = get_num(b[i]);
hc1 = (hc1 - get_num(b[i - a.size()]) * p + mod1) % mod1;
hc1 *= bz; hc1 += x; hc1 %= mod1;
hc2 = (hc2 - get_num(b[i - a.size()]) * p + mod2) % mod2;
hc2 *= bz; 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;
}