Pagini recente » Cod sursa (job #3121782) | Cod sursa (job #3145217) | Cod sursa (job #3267704) | Cod sursa (job #420797) | Cod sursa (job #925443)
Cod sursa(job #925443)
#include <string>
#include <vector>
#include <fstream>
#include <iterator>
#include <algorithm>
using namespace std;
const int NMAX = 2000011;
const int SOLMAX = 1000;
const int MODULO1 = 100003;
const int MODULO2 = 300007;
const int Alpha = 31;
const int Beta = 73;
vector<int> matchIdx;
inline int min(const int& x, const int& y) {return x <= y ? x : y;}
void solve(string& pattern, string& s)
{
int N, M, A, B, i, pHashA, pHashB, sHashA, sHashB;
N = s.size();
M = pattern.size();
A = B = 1;
pHashA = pHashB = sHashA = sHashB = 0;
for(i = 0; i < M; ++i)
{
pHashA = ( (1LL * pHashA * Alpha) % MODULO1 + pattern[i]) % MODULO1;
pHashB = ( (1LL * pHashB * Beta) % MODULO2 + pattern[i]) % MODULO2;
sHashA = ( (1LL * sHashA * Alpha) % MODULO1 + s[i]) % MODULO1;
sHashB = ( (1LL * sHashB * Beta) % MODULO2 + s[i]) % MODULO2;
if(i)
{
A = (1LL * A * Alpha) % MODULO1;
B = (1LL * B * Beta) % MODULO2;
}
}
if(pHashA == sHashA && pHashB == sHashB)
{
matchIdx.push_back(0);
}
for(; i < N; ++i)
{
sHashA = ( ((sHashA - (1LL * A * s[i - M]) % MODULO1 + MODULO1) * Alpha)%MODULO1 + s[i]) % MODULO1;
sHashB = ( ((sHashB - (1LL * B * s[i - M]) % MODULO2 + MODULO2) * Beta)%MODULO2 + s[i]) % MODULO2;
if(pHashA == sHashA && pHashB == sHashB)
{
matchIdx.push_back(i - M + 1);
}
}
}
int main()
{
string s, pattern;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
getline(in, pattern);
getline(in, s);
solve(pattern, s);
out << matchIdx.size() << '\n';
copy(matchIdx.begin(), matchIdx.begin() + min(SOLMAX, matchIdx.size()), ostream_iterator<int>(out, " "));
out << '\n';
return EXIT_SUCCESS;
}