Pagini recente » Cod sursa (job #795511) | Cod sursa (job #1238930) | Cod sursa (job #2625316) | Cod sursa (job #922665) | Cod sursa (job #3004095)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const long long mod = 1000007;
const long long baza = 30;
long long power = 1;
int hashh(string s)
{
long long r = 0;
for (long long i = 0; i < s.size(); i++)
{
r = r * baza + s[i];
r %= mod;
}
return r;
}
vector<long long> poz;
void rabin_karp(string sir, string pat)
{
long long cnt = 0;
long long h1 = hashh(pat);
long long h2 = 0;
for (long long i = 0; i < pat.size(); i++)
{
power = (power * baza) % mod;
}
for (long long i = 0; i < sir.size(); i++)
{
h2 = h2 * baza + sir[i];
h2 %= mod;
if (i >= pat.size())
{
h2 -= (power * sir[i - pat.size()]) % mod;
if (h2 < 0)
{
h2 += mod;
}
}
if (i >= pat.size() - 1 && h1 == h2)
{
bool ok = true;
for (int j = 0; j < pat.size(); j++)
{
if (sir[i - j] != pat[j])
{
ok = false;
break;
}
}
if (ok)
{
cnt++;
poz.push_back(i - pat.size() + 1);
}
}
}
fout << cnt << '\n';
for (long long i = 0; i < poz.size(); i++)
{
fout << poz[i] << ' ';
}
}
int main()
{
string sir, pat;
fin >> pat >> sir;
rabin_karp(sir, pat);
return 0;
}