Pagini recente » Cod sursa (job #2661675) | Cod sursa (job #1329616) | Cod sursa (job #533213) | Cod sursa (job #611493) | Cod sursa (job #2739229)
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
std::ifstream f("strmatch.in");
std::ofstream g("strmatch.out");
typedef unsigned long long ULL;
const int MOD = 666013;
const int prime = 13;
unsigned hash(const std::string& s, int start, int end)
{
unsigned h = 0, p = 1;
for (int i = end; i>=start;--i)
{
h = (h + s[i] * p) % MOD;
p = (p * prime) % MOD;
}
return h;
}
void find(const std::string& s, const std::string& pattern)
{
int patSize = pattern.size();
int sSize = s.size();
int count = 0;
int apar[1000];
unsigned pathash = hash(pattern, 0, patSize - 1);
unsigned shash = hash(s, 0, patSize - 1);
unsigned p = 1;
for (int i = 1; i < patSize; i++)
p = (p * prime) % MOD;
for (int i = 0; i <= sSize - patSize; ++i)
{
if(i == 474)
std::cout << pathash << ' ' << shash << '\n';
if (pathash == shash)
{
bool ok = true;
for (int k = 0; ok && k < patSize; ++k)
if (s[i + k] != pattern[k])ok = false;
if (ok)
{
apar[count++] = i;
if (count == 1000)
{
break;
}
}
}
if (i + patSize < sSize)
shash = ((shash - (p * s[i]) % MOD + MOD) * prime + s[i + patSize]) % MOD;
}
g << count << '\n';
for (int i = 0; i < count; ++i)
g << apar[i] << ' ';
}
int main()
{
std::string s, p;
f >> p >> s;
find(s, p);
}