Pagini recente » Cod sursa (job #387657) | Cod sursa (job #682166) | Cod sursa (job #302518) | Cod sursa (job #152215) | Cod sursa (job #3264976)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int MOD = 1'000'000'007;
const int MAX_N = 2'000'000;
const int MAX_AP = 1'000;
const int BASE = 127;
long long textHash[MAX_N + 1], pwr[MAX_N + 1];
long long patternHash, leftHash, rightHash, currHash;
int patternLen, textLen, nr;
int pos[MAX_AP + 1];
int main()
{
string pattern, text;
f >> pattern >> text;
patternLen = pattern.size();
textLen = text.size();
pwr[0] = 1;
for (int i = 1; i <= MAX_N; i++)
pwr[i] = (pwr[i - 1] * BASE) % MOD;
patternHash = 0;
for (int i = 0; i < patternLen; i++)
{
patternHash *= BASE;
patternHash += (pattern[i] - '0');
patternHash %= MOD;
}
for (int i = 0; i < textLen; i++)
{
textHash[i + 1] = textHash[i];
textHash[i + 1] *= BASE;
textHash[i + 1] += (text[i] - '0');
textHash[i + 1] %= MOD;
}
for (int i = patternLen; i <= textLen; i++)
{
rightHash = textHash[i];
leftHash = (pwr[patternLen] * textHash[i - patternLen]) % MOD;
currHash = (rightHash - leftHash + MOD) % MOD;
if (currHash == patternHash)
{
++nr;
if (nr <= MAX_AP)
pos[nr] = i - patternLen;
}
}
g << nr << '\n';
for (int i = 1; i <= nr; i++)
g << pos[i] << ' ';
f.close();
g.close();
return 0;
}