Pagini recente » Cod sursa (job #875420) | Cod sursa (job #533229) | Cod sursa (job #598694) | Cod sursa (job #2157421) | Cod sursa (job #3184394)
//Rares 0net
using namespace std;
using LL=long long;
#ifdef RS
#include "Rares0.hpp"
#else
#include<string>
#include<vector>
#include<fstream>
using namespace std;
const string N_file="strmatch";
ifstream fin(N_file+".in");
ofstream fout(N_file+".out");
#define cin fin
#define cout fout
#endif
#define endl '\n'
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define f first
#define s second
#define INF 0x3f3f3f3f
void RSinit()
{
cin.tie(0)->sync_with_stdio(false);
cout.tie(0);
}
#define MOD1 100007
#define MOD2 100021
#define v 73
pair<int, int>rollingHash(const string &str)
{
int hash_val1, hash_val2;
hash_val1=hash_val2=0;
int n=str.size();
for(int i=0; i<n; ++i)
{
hash_val1=(1LL*hash_val1*v+str[i])%MOD1;
hash_val2=(1LL*hash_val2*v+str[i])%MOD2;
}
return mp(hash_val1, hash_val2);
}
LL ModPow(LL base, LL exp, LL mod)
{
LL ans=1;
while(exp>0)
{
if(exp%2==1)
ans=(ans*base)%mod;
base=(base*base)%mod;
exp/=2;
}
return ans;
}
vector<int>RabinKarp(const string &str, const string &SIR)
{
int M=str.size();
int N=SIR.size();
vector<int>Pos;
pair<int, int>hash_A=rollingHash(str);
pair<int, int>hash_B=rollingHash(SIR.substr(0, M));
for(int i=0; i<=N-M; ++i)
{
if(hash_A==hash_B)
Pos.pb(i);
if(i<N-M)
{
hash_B.f=(1LL*(hash_B.f-1LL*SIR[i]*ModPow(v, M-1, MOD1))*v+SIR[i+M])%MOD1;
hash_B.s=(1LL*(hash_B.s-1LL*SIR[i]*ModPow(v, M-1, MOD2))*v+SIR[i+M])%MOD2;
if(hash_B.f<0)
hash_B.f=(hash_B.f+MOD1);
if(hash_B.s<0)
hash_B.s=(hash_B.s+MOD2);
}
}
return Pos;
}
string str, SIR;
vector<int>SolPos;
void Solve()
{
cin>>str>>SIR;
SolPos=RabinKarp(str, SIR);
cout<<(int)SolPos.size()<<endl;
for(int i=0; i<min((int)SolPos.size(), 1000); ++i)
cout<<SolPos[i]<<' ';
}
main()
{
RSinit();
Solve();
}