Pagini recente » Cod sursa (job #809284) | Cod sursa (job #2710108) | Cod sursa (job #2770595) | Cod sursa (job #1903267) | Cod sursa (job #2853106)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream file_in("strmatch.in");
ofstream file_out("strmatch.out");
string A, B;
vector<int> AP;
constexpr int MOD = 101, MAX = 260;
int i, j, CNT;
void RabinKarp(string PAT, string TXT)
{
size_t M = PAT.length();
size_t N = TXT.length();
int P = 0, T = 0, H = 1;
bool flag;
for (i = 0; i < M - 1; ++i)
H = (H * MAX) % MOD;
for (i = 0; i < M; ++i)
{
P = (MAX * P + PAT[i]) % MOD;
T = (MAX * T + TXT[i]) % MOD;
}
for (i = 0; i <= N - M; ++i)
{
if (P == T)
{
for (j = 0; j < M; ++j)
if (TXT[i + j] != PAT[j]) break;
if (j == M)
{
++CNT;
if(CNT <= 1000) AP.push_back(i);
}
}
if (i < N - M)
{
T = (MAX * (T - TXT[i] * H) + TXT[i + M]) % MOD;
if (T < 0) T += MOD;
}
}
}
int main()
{
file_in >> A >> B;
RabinKarp(A, B);
file_out << CNT << '\n';
for (auto it : AP) file_out << it << ' ';
return 0;
}