Pagini recente » Cod sursa (job #2621892) | Cod sursa (job #893615) | Cod sursa (job #1689249) | Cod sursa (job #2672050) | Cod sursa (job #3291683)
#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, p1, p2;
vector<int> aux;
int get_num(char x){
return x - 'A' + 1;
}
int main()
{
f >> a >> b;
if(b.size() < a.size()){
g << 0;
return 0;
}
p1 = p2 = 1;
for(int i = 0; i < a.size(); i ++)
{
int x = get_num(a[i]);
h1 *= bz; h1 += x;
h2 *= bz; h2 += x;
h1 %= mod1; h2 %= mod2;
if(i > 0){
p1 = (p1 * bz) % mod1;
p2 = (p2 * bz) % mod2;
}
}
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()]) * p1 % mod1 + mod1) % mod1;
hc1 *= bz; hc1 += x; hc1 %= mod1;
hc2 = (hc2 - get_num(b[i - a.size()]) * p2 % mod2 + 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;
}