Pagini recente » Cod sursa (job #2177506) | Cod sursa (job #525590) | Cod sursa (job #2161881) | Cod sursa (job #1033275) | Cod sursa (job #1274291)
#include <cstdlib>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int logpow(int base, int e)
{
const int MOD = 1e9 + 7;
if (base == 1 || base == 0)
return base;
base %= MOD;
if (e == 1)
return base;
int square = (base * base) % MOD;
if (e % 2 == 0)
return logpow(square, e / 2) % MOD;
else
return (base * (logpow(square, e / 2) % MOD)) % MOD;
}
int hashFun(int currHash, int length, char prevChar, char nextChar)
{
const int kPrimeBase = 257;
const int MOD = 1e9 + 7;
currHash = ((currHash * kPrimeBase) % MOD);
currHash = abs(currHash - (prevChar * logpow(kPrimeBase, length) % MOD)) % MOD;
currHash = (currHash + nextChar) % MOD;
return currHash;
}
void matchStrings(string& s, string& p, vector<int>& matches)
{
size_t n = s.size(), m = p.size();
int hs = 0, hp = 0;
for (size_t i = 0; i < m; ++i)
{
hs = hashFun(hs, i, '\0', s[i]);
hp = hashFun(hp, i, '\0', p[i]);
}
for (size_t i = 0; i < n - m + 1; ++i)
{
//Compute new hash
if (i > 0)
hs = hashFun(hs, m, s[i - 1], s[i + m - 1]);
//Hashes match
if (hs == hp && matches.size() < 1000)
matches.push_back(i);
}
}
int main()
{
string s, p;
fin >> p >> s;
vector<int> matches;
if (p.size() < s.size())
matchStrings(s, p, matches);
else if (p.size() == s.size())
if (p == s)
matches.push_back(0);
fout << matches.size() << '\n';
for (size_t i = 0; i < matches.size(); ++i)
fout << matches[i] << ' ';
fout << '\n';
return 0;
}