Pagini recente » Cod sursa (job #1659223) | Cod sursa (job #1708111) | Cod sursa (job #1218842) | Cod sursa (job #103834) | Cod sursa (job #2368621)
#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 = 1e9 + 7;
const int MOD2 = 1e9 + 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;
for (int i = 0; i < 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 < 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 = pattern.size(); i < text.size(); ++i)
{
hash_t1 = ((hash_t1 - (text[i - pattern.size()] * base1) % MOD1 + MOD1) * BASE + text[i]) % MOD1;
hash_t2 = ((hash_t2 - (text[i - pattern.size()] * base2) % MOD2 + MOD2) * BASE + text[i]) % MOD2;
if (hash_p1 == hash_t1 && hash_p2 == hash_t2)
ans.pb(i - pattern.size() + 1);
}
int cnt = 0;
fout << ans.size() << '\n';
for (int i: ans)
{
fout << i << ' ';
++cnt;
if (cnt > 1000) break;
}
return 0;
}