Pagini recente » Cod sursa (job #1958320) | Cod sursa (job #640839) | Cod sursa (job #1943921) | Cod sursa (job #2096819) | Cod sursa (job #2721832)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
const long long p = 73;
const long long MODULO1 = 100007;
const long long MODULO2 = 100021;
const int SOLDIMMAX = 1000;
string sir1, sir2;
vector<int> sol;
/// Rabin-Karp
int main()
{
ifstream in("strmatch.in");
ofstream out("strmatch.out");
in >> sir1 >> sir2;
long long hash1 = 0;
long long hash2 = 0;
long long p1 = 1;
long long p2 = 1;
for (int i = 0; i < sir1.size(); i++)
{
hash1 = (hash1 * p + sir1[i]) % MODULO1;
hash2 = (hash2 * p + sir1[i]) % MODULO2;
if (i > 0)
{
p1 = (p1 * p) % MODULO1;
p2 = (p2 * p) % MODULO2;
}
}
if (sir1.size() > sir2.size())
{
out << 0 << '\n';
return 0;
}
long long nrAparitii = 0;
long long hash1Crt = 0;
long long hash2Crt = 0;
for (int i = 0; i < sir1.size(); i++)
{
hash1Crt = (hash1Crt * p + sir2[i]) % MODULO1;
hash2Crt = (hash2Crt * p + sir2[i]) % MODULO2;
}
if (hash1 == hash1Crt && hash2 == hash2Crt)
{
nrAparitii++;
sol.emplace_back(0);
}
for (int i = sir1.size(); i < sir2.size(); i++)
{
hash1Crt = ((hash1Crt - (p1 * sir2[i - sir1.size()]) % MODULO1 + MODULO1) * p + sir2[i]) % MODULO1;
hash2Crt = ((hash2Crt - (p2 * sir2[i - sir1.size()]) % MODULO2 + MODULO2) * p + sir2[i]) % MODULO2;
if (hash1 == hash1Crt && hash2 == hash2Crt)
{
nrAparitii++;
if (nrAparitii <= SOLDIMMAX)
{
sol.emplace_back(i - sir1.size() + 1);
}
}
}
out << nrAparitii << '\n';
for (int i = 0; i < sol.size(); i++)
{
out << sol[i] << ' ';
}
return 0;
}