Pagini recente » Cod sursa (job #423995) | Cod sursa (job #1130121) | Cod sursa (job #1958920) | Cod sursa (job #1821593) | Cod sursa (job #2679047)
#include<bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef long double ld;
const int hmod = 1e9 + 123;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int mx_pow = 0, my_base;
int gen_base(const int before, const int after) {
auto seed = std::chrono::high_resolution_clock::now().time_since_epoch().count();
std::mt19937 mt_rand(seed);
int base = std::uniform_int_distribution<int>(before+1, after)(mt_rand);
return base % 2 == 0 ? base-1 : base;
}
struct p_hash {
vector<int> pow1, pre1;
vector<unsigned ll> pow2, pre2;
int base, mx_pow;
void assign_bases(int x, int y) {
base = x;
mx_pow = y;
}
void build(string s) {
pre1.assign((int)s.size() + 1, 0);
pre2.assign((int)s.size() + 1, 0);
int n = s.size();
//cout << base << '\n';
pow1.push_back(1);
pow2.push_back(1);
while(pow1.size() <= mx_pow) {
pow1.push_back( 1LL * pow1.back() * base % hmod);
pow2.push_back(pow2.back() * base);
}
for(int i = 0; i < n; i++) {
pre1[i + 1] = (pre1[i] + 1LL * (s[i]) * pow1[i]) % hmod;
pre2[i + 1] = pre2[i] + (s[i]) * pow2[i];
}
}
pair<int,unsigned long long> get(int pos, int len) {
int hash1 = pre1[pos + len] - pre1[pos];
unsigned long long hash2 = pre2[pos + len] - pre2[pos];
if(hash1 < 0) hash1 += hmod;
if(mx_pow > 0) {
hash1 = 1ll * hash1 * pow1[mx_pow - (pos + len - 1)] % hmod;
hash2 *= pow2[mx_pow - (pos + len - 1)];
}
return make_pair(hash1, hash2);
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
string s, t;
in >> t >> s;
mx_pow = max(s.size(), t.size());
my_base = gen_base('z' + 1, hmod);
//poly_hash A, B;
p_hash A, B;
A.assign_bases(my_base, mx_pow);
B.assign_bases(my_base, mx_pow);
A.build(s);
B.build(t);
int cnt = 0;
vector<int> ans;
auto me = B.get(0, (int) t.size());
for(int i = 0; i + (int) t.size() <= (int) s.size(); i++) {
auto his = A.get(i, (int) t.size());
//cout << me.first << ' ' << his.first << '\n';
if(me == his && cnt < 1000) {
ans.pb(i);
if(cnt == 1000) break;
}
}
out << ans.size() << '\n';
for(auto it : ans) out << it << ' ';
return 0;
}