Pagini recente » Cod sursa (job #3362381) | Cod sursa (job #3362466)
#include <bits/stdc++.h>
using namespace std;
ifstream in ("strmatch.in");
ofstream out ("strmatch.out");
string a, b;
const long long BASE = 31;
const long long MOD = 1000000021;
long long hashing(const string& s)
{
long long val = 0;
for (int i = 0; i < s.size(); i++)
{
val = (val * BASE % MOD + (unsigned char)s[i]) % MOD;
}
return val;
}
long long nr;
vector <int> poz;
int main()
{
in >> a >> b;
long long ans = hashing(a);
long long rez = 0;
for (int i = 0; i < a.size(); i++)
{
rez = (rez * BASE % MOD + (unsigned char)b[i]) % MOD;
}
if(ans == rez)
{
poz.push_back(0);
nr++;
}
long long BASEE = 1;
for (int i = 0; i < a.size() - 1; i++)
{
BASEE = (BASEE * BASE) % MOD;
}
for (int i = a.size(); i < b.size(); i++)
{
rez = (rez - ((unsigned char)b[i - a.size()] * BASEE % MOD) + MOD) % MOD;
rez = rez * BASE % MOD;
rez = (rez + (unsigned char)b[i]) % MOD;
if (rez == ans)
{
nr++;
poz.push_back(i - a.size() + 1);
}
}
out << nr << "\n";
for (int i = 0; i < min(1000LL, (long long)poz.size()); i++)
{
out << poz[i] << " ";
}
return 0;
}