Pagini recente » Monitorul de evaluare | Istoria paginii utilizator/shaghi | Diferente pentru home intre reviziile 774 si 773 | Cod sursa (job #1295566) | Cod sursa (job #2284540)
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
typedef long long yourmom;
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];
yourmom Kapow(yourmom a, int p, yourmom m)
{
yourmom r = 1;
for(int i = 0; i < p; i++){
r *= a;
r %= m;
}
return r;
}
struct Thing{
yourmom n, m, p;
Thing(yourmom n, yourmom m) : n(n), m(m){}
void GenP()
{
this->p = Kapow(n, lolle-1, m);
}
};
Thing t1(41, 200041), t2(43, 204141);
void Read()
{
getline(in, a);
getline(in, b);
lolle = a.size();
t1.GenP(); t2.GenP();
}
yourmom GenHash(const Thing & t, const string & s)
{
yourmom 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
void Roll(yourmom & h, const Thing & t, const int & pos)
{
h = (h - b[pos] * t.p) % t.m;
// h -= b[pos] * t.p;
// h %= t.m;
h = ((h + t.m) * t.n) % t.m;
// h += t.m;
// h *= t.n;
// h %= t.m;
h = (h + b[pos+lolle]) % t.m;
// h += b[pos + lolle];
// h %= t.m;
}
void Solve()
{
yourmom c1 = GenHash(t1, a), c2 = GenHash(t2, a);
yourmom h1 = GenHash(t1, b), h2 = GenHash(t2, b);
int idk = b.size();
for(int i = 0; i < idk-lolle-1; i++){
if(c1 == h1 && c2 == h2){
if(anslen < 1000){
ans[anslen] = i;
}
anslen++;
}
Roll(h1, t1, i);
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;
}