Pagini recente » Cod sursa (job #925646) | Cod sursa (job #2893385) | Cod sursa (job #1559630) | Cod sursa (job #454362) | Cod sursa (job #2284310)
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
istream & in = fin;
ostream & out = fout;
string a, b;
int lolle;
int anslen = 0;
int ans[1041];
int Kapow(int a, int p)
{
int r = 1;
for(int i = 0; i < p; i++){
r *= a;
}
return r;
}
struct Thing{
int n, m, p;
Thing(int n, int m) : n(n), m(m){}
void GenP()
{
this->p = Kapow(n, lolle-1);
}
};
Thing t1(3, 2000000041), t2(5, 2000004141);
void Read()
{
getline(in, a);
getline(in, b);
lolle = a.size();
t1.GenP(); t2.GenP();
}
int GenHash(const Thing & t, const string & s)
{
int h = 0;
for(auto i = s.begin(); i < s.begin()+lolle; i++){
h *= t.n;
h += *i;
h %= t.m;
}
return h;
}
//they see me rolling
int Roll(int h, const Thing & t, int pos)
{
h -= b[pos] * t.p;
h *= t.n;
h += b[pos + lolle];
h %= t.m;
return h;
}
void Solve()
{
int c1 = GenHash(t1, a), c2 = GenHash(t2, a);
int h1 = GenHash(t1, b), h2 = GenHash(t2, b);
int idk = b.size();
for(int i = 0; i < idk-lolle; i++){
if(c1 == h1 && c2 == h2){
if(anslen < 1000){
ans[anslen] = i;
}
anslen++;
}
h1 = Roll(h1, t1, i);
h2 = Roll(h2, t2, i);
}
}
void Write()
{
out << anslen << "\n";
for(int i = 0; i < anslen; i++){
out << ans[i] << " ";
}
}
int main()
{
Read();
Solve();
Write();
return 0;
}