Pagini recente » Cod sursa (job #443294) | Cod sursa (job #585349) | Cod sursa (job #2254486) | Cod sursa (job #3192118) | Cod sursa (job #2368711)
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define enter cout << '\n'
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <int> vi;
typedef vector <pii> vii;
typedef vector <ll> vl;
typedef vector <pll> vll;
typedef queue <int> qi;
typedef queue <pii> qii;
typedef queue <ll> ql;
typedef queue <pll> qll;
const int INF = 0x3f3f3f3f;
const int MOD = 100003;
const int MOD1 = 1e5 + 7;
const int MOD2 = 1e5 + 21;
const int BASE = 73;
const double EPSILON = 1e-10;
const int NMAX = 5e4 + 5;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string pattern, text;
int hash_p1, hash_p2, hash_t1, hash_t2, base1 = 1, base2 = 1;
vi ans;
int main()
{
fin >> pattern >> text;
if ((int)pattern.size() > (int)text.size())
{
fout << "0\n";
return 0;
}
for (int i = 0; i < (int)pattern.size(); ++i)
{
hash_p1 = (hash_p1 * BASE + pattern[i]) % MOD1;
hash_p2 = (hash_p2 * BASE + pattern[i]) % MOD2;
if (i != 0)
{
base1 = (base1 * BASE) % MOD1;
base2 = (base2 * BASE) % MOD2;
}
}
for (int i = 0; i < (int)pattern.size(); ++i)
{
hash_t1 = (hash_t1 * BASE + text[i]) % MOD1;
hash_t2 = (hash_t2 * BASE + text[i]) % MOD2;
}
if (hash_p1 == hash_t1 && hash_p2 == hash_t2)
ans.pb(0);
for (int i = (int)pattern.size(); i < (int)text.size(); ++i)
{
hash_t1 = (((hash_t1 - (text[i - (int)pattern.size()] * base1) % MOD1 + MOD1) * BASE) % MOD1 + text[i]) % MOD1;
hash_t2 = (((hash_t2 - (text[i - (int)pattern.size()] * base2) % MOD2 + MOD2) * BASE) % MOD2 + text[i]) % MOD2;
if (hash_p1 == hash_t1 && hash_p2 == hash_t2)
ans.pb(i - (int)pattern.size() + 1);
}
fout << ans.size() << '\n';
for (int i = 0; i < 1000 && i < ans.size(); ++i)
fout << ans[i] << ' ';
return 0;
}