Pagini recente » Diferente pentru home intre reviziile 588 si 902 | Cod sursa (job #445840) | Monitorul de evaluare | Cod sursa (job #2247111) | Cod sursa (job #2736005)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int p1 = 666013;
const int p2 = 666019;
vector <int> sol;
string A, B;
int main()
{
in >> A >> B;
int n = A.size();
int m = B.size();
int hshA1 = 0;
int hshA2 = 0;
int put1 = 1;
int put2 = 1;
for(int i = 0; i < n; i++)
{
hshA1 = (26LL * hshA1 + A[i]) % p1;
hshA2 = (26LL * hshA2 + A[i]) % p2;
}
cerr << hshA1 << " " << hshA2 << "\n";
long long act1 = 0;
long long act2 = 0;
for(int i = 0; i < min(n - 1, m); i++)
{
act1 = (26LL * act1 + B[i]) % p1;
act2 = (26LL * act2 + B[i]) % p2;
put1 = (put1 * 26) % p1;
put2 = (put2 * 26) % p2;
}
for(int i = n - 1; i < m; i++)
{
act1 = (26LL * act1 + B[i]) % p1;
act2 = (26LL * act2 + B[i]) % p2;
cerr << act1 << " " << act2 << "\n";
if(act1 == hshA1 && act2 == hshA2)
sol.push_back(i - n + 1);
act1 = (act1 - put1 * B[i - n + 1] % p1 + p1) % p1;
act2 = (act2 - put2 * B[i - n + 1] % p2 + p2) % p2;
}
out << sol.size() << "\n";
for(int i = 0; i < min(1000, (int)sol.size()); i++)
out << sol[i] << " ";
out << "\n";
return 0;
}