Pagini recente » Cod sursa (job #1940945) | Cod sursa (job #2282425) | Sport | Cod sursa (job #1224744) | Cod sursa (job #2449984)
#include <fstream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int alphabethSize = 256;
const int maxTextSize = 2000005;
vector <int> indices;
void rabinKarpSearch(char pattern[], char text[], const int Mod);
char text[maxTextSize];
char pattern[maxTextSize];
int main()
{
fin >> pattern >> text;
const int Mod = 101;
rabinKarpSearch(pattern, text, Mod);
const int nrOfApparitions = indices.size();
fout << nrOfApparitions << '\n';
for (int i = 0; i < min(nrOfApparitions, 1000); ++i)
fout << indices[i] << ' ';
fin.close();
fout.close();
return 0;
}
void rabinKarpSearch(char pattern[], char text[], int Mod)
{
int patternSize = strlen(pattern);
int textSize = strlen(text);
int hvPattern = 0;
int hvText = 0;
int h = 1;
for (int i = 0; i < patternSize - 1; ++i)
h = (h * alphabethSize) % Mod;
for (int i = 0; i < patternSize; ++i)
{
hvPattern = (alphabethSize * hvPattern + pattern[i]) % Mod;
hvText = (alphabethSize * hvText + text[i]) % Mod;
}
for (int i = 0; i <= textSize - patternSize; ++i)
{
if (hvPattern == hvText)
{
int j;
for (j = 0; j < patternSize; ++j)
{
if (text[i + j] != pattern[j])
break;
}
if (j == patternSize)
indices.push_back(i);
}
if (i < textSize - patternSize)
{
hvText = (alphabethSize * (hvText - text[i] * h) + text[i + patternSize]) % Mod;
if (hvText < 0)
hvText += Mod;
}
}
}