Pagini recente » Cod sursa (job #915330) | Cod sursa (job #1672775) | Cod sursa (job #1174230) | Cod sursa (job #525078) | Cod sursa (job #2736000)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int p1 = 666013;
const int p2 = 100007;
vector <int> sol;
string A, B;
int lgput1(int a, int b)
{
if(b == 0)
return 1;
int p = lgput1(a, b / 2);
if(b % 2 == 0)
return p * p % p1;
return (p * p % p1) * a % p1;
}
int lgput2(int a, int b)
{
if(b == 0)
return 1;
int p = lgput2(a, b / 2);
if(b % 2 == 0)
return p * p % p2;
return (p * p % p1) * a % p2;
}
int main()
{
in >> A >> B;
int n = A.size();
int m = B.size();
int hshA1 = 0;
int hshA2 = 0;
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;
}
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 - lgput1(26, n - 1) * B[i - n + 1] + p1) % p1;
act2 = (act2 - lgput2(26, n - 1) * B[i - n + 1] + p2) % p2;
}
out << sol.size() << "\n";
for(int i = 0; i < min(1000, (int)sol.size()); i++)
out << sol[i] << " ";
out << "\n";
return 0;
}