Pagini recente » Cod sursa (job #2656521) | Cod sursa (job #1393236) | Cod sursa (job #597110) | Cod sursa (job #1912610) | Cod sursa (job #3148626)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
static constexpr int BASE[] = {131, 241};
static constexpr int MOD[] = {((int)(1e9) + 7), ((int)(1e9) + 9)};
static constexpr int NMAX = (int)(2e6 + 1);
string A, B;
int n, m;
int p[2][NMAX];
static inline void read()
{
f.tie(nullptr);
A = B = "";
f >> A >> B;
n = (int)A.size(), m = (int)B.size();
return;
}
static inline void multiply(int &a, const int &b, const int &c)
{
if (1LL * a * b >= 1LL * c)
a = (1LL * a * b) % (1LL * c);
else
a *= b;
return;
}
static inline void add(int &a, const int &b, const int &c)
{
a += b;
if (a >= c)
a -= c;
if (a < 0)
a += c;
return;
}
static inline void precompute(const int &n)
{
p[0][0] = p[1][0] = 1;
for (int i = 1; i <= n; ++i)
for (int j = 0; j < 2; ++j)
p[j][i] = p[j][i - 1], multiply(p[j][i], BASE[j], MOD[j]);
return;
}
static inline vector<int> get_hash(const string &S)
{
int size = (int)S.size();
vector<int> v = {0, 0};
for (int i = 0; i < size; ++i)
for (int j = 0; j < 2; ++j)
multiply(v[j], BASE[j], MOD[j]), add(v[j], (int)(S[i]), MOD[j]);
return v;
}
static inline string extract(const string &S, const int &left, const int &right)
{
string ans = "";
for (int i = left; i <= right; ++i)
ans += S[i];
return ans;
}
static inline bool is_match(const vector<int> &a, const vector<int> &b)
{
bool ok = 1;
for (int i = 0; i < 2 && ok; ++i)
if (a[i] == b[i])
continue;
else
ok = 0;
return ok;
}
static inline int my_min(const int &a, const int &b)
{
return ((a < b) ? a : b);
}
int main()
{
read();
precompute(n);
vector<int> first_string = get_hash(A);
vector<int> second_string = get_hash(extract(B, 0, (n - 1)));
vector<int> ans = {};
if (is_match(first_string, second_string))
ans.push_back(0);
for (int i = 1; (i + n - 1) < m; ++i)
{
for (int j = 0; j < 2; ++j)
{
add(second_string[j], -((1LL * (int)(B[i - 1]) * p[j][n - 1]) % (1LL * MOD[j])), MOD[j]);
multiply(second_string[j], BASE[j], MOD[j]);
add(second_string[j], (int)(B[i + n - 1]), MOD[j]);
}
if (is_match(first_string, second_string))
ans.push_back(i);
}
g << (int)ans.size() << '\n';
int m = my_min((int)ans.size(), (int)(1e3));
for (int i = 0; i < m; ++i)
{
g << ans[i];
if (i == (m - 1))
g << '\n';
else
g << ' ';
}
return 0;
}