Pagini recente » Cod sursa (job #1449847) | Cod sursa (job #3225645)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
struct custom_hash_pair {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(pair<uint64_t,uint64_t> x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x.first + FIXED_RANDOM)^(splitmix64(x.second + FIXED_RANDOM) >> 1);
}
};
#define all(x) (x).begin(), (x).end()
#define allg(x) (x).begin(), (x).end(), greater<int>()
using ull = unsigned long long;
using ll = long long;
using ld = double;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<ld>;
using si = set<int>;
using ssi = set<si>;
using sl = set<ll>;
using ssl = set<sl>;
using vvi = vector<vi>;
using vvb = vector<vb>;
using vvl = vector<vl>;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vs = vector<string>;
using vpi = vector<pii>;
using vpl = vector<pll>;
using vvpl = vector<vpl>;
#define umap unordered_map
#define eb emplace_back
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define ff first
#define ss second
#define ar array
inline void yn(bool b)
{
if(b==true)
cout<<"Yes\n";
else
cout<<"No\n";
}
inline void fastio() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
ll Mod = 1e9+7;
inline bool hasbit(ll nr, ll pos)
{
return (nr&(1ll<<pos));
}
const string TASK("strmatch");
ifstream fin(TASK + ".in");
ofstream fout(TASK + ".out");
#define cin fin
#define cout fout
const ll Inf = 0x3f3f3f3f;
bool testCase = false;
const ll Nmax=2e6+10;
ll p = 83;
ll put[Nmax];
ll inv[Nmax];
ll fastexp(ll n,ll x)
{
ll ret = 1;
while(x)
{
if(x&1)
{ret *= n;
ret %= Mod;
x--;}
if(x==0)break;
n *= n;
n %= Mod;
x/=2;
}
return ret;
}
ll hfirst = 0;
ll htab[Nmax];
void solve_testcase()
{
vl ans;
string s1,s2;
cin>>s1>>s2;
int n = s1.size();
int m = s2.size();
for(int i=0;i<n;i++)
{
char c = s1[i];
hfirst += put[i] * (c - 'A' + 1);
hfirst %= Mod;
}
htab[0] = s2[0]-'A'+1;
//cout<<0<<" "<<htab[0]<<endl;
for(int i=1;i<m;i++)
{
char c = s2[i];
htab[i] = htab[i-1] + put[i] * (c-'A'+1);
htab[i] %= Mod;
//cout<<i<<" "<<htab[i]<<endl;
}
for(int i=0;i+n-1<m;i++)
{
if(s2[i]!=s1[0])continue;
ll st = i, dr = i+n-1;
ll scad = 0;
if(st>0)
scad = htab[st-1];
ll hnow = (htab[dr] + Mod - scad) % Mod;
//hnow *= inv[st];
//hnow %= Mod;
//hnow*=put[st];
hnow%=Mod;
//cout<<hnow<<" "<<(hfirst*put[st])%Mod<<endl;
if(hnow==((hfirst*put[st])%Mod))
ans.eb(i);
}
cout<<ans.size()<<'\n';
for(auto c:ans)
cout<<c<<" ";
cout<<'\n';
}
void pregenerate()
{
put[0] = inv[0] = 1;
for(int i=1;i<Nmax;i++)
{put[i] = put[i-1] * p;
put[i] %= Mod;}
//inv[i] = fastexp(put[i],Mod-2);}
}
/// Check for interruption of input!!
/// a+b=a^b+2*(a&b)
int main() {
fastio();
pregenerate();
ll t=1;
if (testCase) cin >> t;
while (t--)
{ //cout<<t<<endl;
solve_testcase();
}
return 0;
}