Pagini recente » Cod sursa (job #608337) | Cod sursa (job #3289613) | Cod sursa (job #2462497) | Cod sursa (job #1116862) | Cod sursa (job #3279036)
#include <iostream>
#include <string>
#include <cstring>
#include <cstdint>
#include <vector>
#include <fstream>
#define int long long
using namespace std;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
class Hash
{
public:
int hsh=0, ptr=0, lim, mod, p, imp=0;
string s;
int lgpow (int a, int b)
{
if (b==0)
return 1;
if (b%2==0)
{
int p=lgpow (a, b/2);
return (p%mod)*(p%mod)%mod;
}
return (lgpow (a, b-1)%mod)*(a%mod)%mod;
}
Hash ()
{
}
void make (string s, int mod, int p)
{
this -> mod=mod;
this -> p=p;
this -> lim=s.size();
this -> s=s;
for (int i=0;i<s.size();i++)
{
hsh+=s[i]*lgpow (p, ((int)s.size()-i-1));
hsh%=mod;
}
this -> imp=lgpow (p, lim-1);
}
void roll (char ch)
{
hsh-=s[this -> ptr++]*imp;
hsh=(hsh+mod)%mod;
hsh*=p;
hsh%=mod;
hsh+=(int)ch;
hsh%=mod;
s+=ch;
}
};
vector <int> vec;
Hash a, a1, b, b1;
string s, s1;
int32_t main ()
{
f >> s >> s1;
a.make (s, 31, 400099);
b.make (string (s1.begin(), s1.begin()+s.size()), 31, 400099);
a1.make (s, 53, 310993);
b1.make (string (s1.begin(), s1.begin()+s.size()), 53, 310993);
if (a.hsh==b.hsh && a1.hsh==b1.hsh)
{
vec.push_back (0);
}
for (int i=(int)s.size();i<s1.size();i++)
{
b.roll (s1[i]);
b1.roll (s1[i]);
if (a.hsh==b.hsh && a1.hsh==b1.hsh)
{
vec.push_back (i-s.size()+1);
}
}
g << vec.size() << "\n";
for (int i=0;i<vec.size() && i<1000;i++)
{
g << vec[i] << " ";
}
return 0;
}