Pagini recente » Cod sursa (job #588764) | Profil lawandaff2316 | Cuvinte 2 | Istoria paginii utilizator/kinda_93 | Cod sursa (job #2532893)
#include <fstream>
#include <string>
#include <vector>
#define input "strmatch.in"
#define output "strmatch.out"
#define D 128
#define Q 131
using namespace std;
ifstream in(input);
ofstream out(output);
string A, B;
vector < int > sol;
int M, N;
int fasto_expo(int base, int exp)
{
if(!exp) return 1;
if(exp == 1) return base % Q;
if(exp % 2) return base * fasto_expo((base * base) % Q, exp / 2) % Q;
return fasto_expo((base * base) % Q, exp / 2) % Q;
}
void Read_Data()
{
in >> A >> B;
M = A.size();
N = B.size();
}
bool Manual_Check(int k)
{
for(int i = 0; i < M; i++)
if(A[i] != B[i + k]) return false;
return true;
}
void Rabin_Karp()
{
int h = fasto_expo(D, M - 1) % Q, P = 0, T0 = 0;
for(int i = 0; i < M; i++)
{
P = (D * P + A[i]) % Q;
T0 = (D * T0 + B[i]) % Q;
}
for(int k = 0; k <= N - M; k++)
{
if(P == T0)
if(Manual_Check(k)) sol.push_back(k);
T0 = (T0 + D * Q - B[k] * h + 2 * Q) % Q;
T0 = (T0 * D + B[k + M]) % Q;
}
}
void Print_Sol()
{
out << sol.size() << "\n";
int a = sol.size();
for(unsigned i = 0; i < min(a, 1000); i++)
out << sol[i] << " ";
}
int main()
{
Read_Data();
Rabin_Karp();
Print_Sol();
return 0;
}