Pagini recente » Cod sursa (job #1657945) | Cod sursa (job #797196) | Cod sursa (job #2886544) | Cod sursa (job #1655079) | Cod sursa (job #1428876)
#include <bits/stdc++.h>
using namespace std;
template <const int MOD, const int BASE>
class RollingHash
{
/**
MOD * BASE < INT.MAX_VALUE
BASE * BASE < INT.MAX_VALUE
MOD * SIGMA < INT.MAX_LALUE
**/
public:
int code;
int base;
RollingHash(const int length = 0) : code(0), base(1) {
for (int i = 1; i < length; ++i)
base = (base * BASE) % MOD;
}
void pop_front(const char ch)
{
code = (code - (base * ch) % MOD + MOD) % MOD; ///POSSIBLE OVERFLOW
}
void push_back(const char ch)
{
code = (code * BASE) % MOD; ///POSSIBLE OVERFLOW
code = (code + ch) % MOD;
}
bool operator == (const RollingHash& R) const
{
return this->code == R.code;
}
bool operator != (const RollingHash& R) const
{
return this->code != R.code;
}
};
const int Nmax = 2000000 + 1;
char A[Nmax], B[Nmax];
int N, M;
int main()
{
ifstream in("strmatch.in");
ofstream out("strmatch.out");
in >> A >> B;
N = strlen(A);
M = strlen(B);
RollingHash<727733, 73> A1(N);
RollingHash<727733, 73> B1(N);
RollingHash<375223, 91> A2(N);
RollingHash<375223, 91> B2(N);
if (N > M)
{
out << "0\n";
return 0;
}
for (int i = 0; i < N; ++i)
{
A1.push_back(A[i]);
A2.push_back(A[i]);
B1.push_back(B[i]);
B2.push_back(B[i]);
}
vector<int> sol;
if (A1 == B1 && A2 == B2)
sol.push_back(0);
for (int i = N; i < M; ++i)
{
B1.pop_front(B[i - N]);
B1.push_back(B[i]);
B2.pop_front(B[i - N]);
B2.push_back(B[i]);
if (A1 == B1 && A2 == B2)
sol.push_back(i - N + 1);
}
out << sol.size() << "\n";
for (int i = 0; i < min(1000, (int)sol.size()); ++i)
out << sol[i] << " ";
out << "\n";
return 0;
}