Pagini recente » Cod sursa (job #297200) | Cod sursa (job #1357875) | Cod sursa (job #520484) | Cod sursa (job #971003) | Cod sursa (job #2244317)
#include <fstream>
#include <vector>
#include <algorithm>
#define MOD_1 100007
#define MOD_2 100021
#define BASE 37
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int main()
{
string A, B;
vector<int> sol;
int hash_A1 = 0, hash_A2 = 0;
int hash_B1 = 0, hash_B2 = 0;
int cnst_A1 = 1, cnst_A2 = 1;
in >> A >> B;
if (A.size() > B.size())
{
out << 0;
return 0;
}
for (int i = 0; i < A.size(); i++)
{
hash_A1 = (hash_A1 * BASE + A[i]) % MOD_1;
hash_A2 = (hash_A2 * BASE + A[i]) % MOD_2;
if (i)
{
cnst_A1 = (cnst_A1 * BASE) % MOD_1;
cnst_A2 = (cnst_A2 * BASE) % MOD_2;
}
}
for (int i = 0; i < A.size(); i++)
{
hash_B1 = (hash_B1 * BASE + B[i]) % MOD_1;
hash_B2 = (hash_B2 * BASE + B[i]) % MOD_2;
}
if (hash_A1 == hash_B1 && hash_A2 == hash_B2)
sol.push_back(0);
for (int i = A.size(); i < B.size(); i++)
{
hash_B1 = ((hash_B1 - (B[i - A.size()] * cnst_A1) % MOD_1 + MOD_1) * BASE + B[i]) % MOD_1;
hash_B2 = ((hash_B2 - (B[i - A.size()] * cnst_A2) % MOD_2 + MOD_2) * BASE + B[i]) % MOD_2;
if (hash_A1 == hash_B1 && hash_A2 == hash_B2)
sol.push_back(i - A.size() + 1);
}
int Size = sol.size();
out << Size << '\n';
for (int i = 0; i < min(1001, Size); i++)
out << sol[i] << ' ';
return 0;
}