Pagini recente » Cod sursa (job #2607217) | Cod sursa (job #3177191)
#include<bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define int __int128
int B;
const int MOD = 1e9+7;
struct HashedString{
vector<int> hash,p;
string s;
HashedString(string S){
s = '_' + S;
hash.resize(s.size()+1);
p.push_back(1);
for(int i=1;i<=S.size()+3;++i){
p.push_back(((p.back()%MOD) * (B%MOD)) % MOD);
}
for(int i=1;i<=s.size()-1;++i){
hash[i] = (((hash[i-1]%MOD) * (B%MOD)) + s[i]) % MOD;
}
}
long long getHash(int st ,int dr){
long long raw_val = (hash[dr] - ((hash[st-1]%MOD) * (p[dr-st+1]%MOD))%MOD + MOD) % MOD;
return raw_val % MOD;
}
};
signed main() {
srand(time(nullptr));
B = rand();
string a,b;
fin >> a >> b;
int n = a.size();
int m = b.size();
HashedString hash_a(a);
HashedString hash_b(b);
long long A_HASH = hash_a.getHash(1,n);
long long st=1,dr=n;
vector<long long> ap;
while(dr<=m){
if(hash_b.getHash(st,dr) == A_HASH){
ap.push_back(st-1);
}
st++,dr++;
}
fout<<ap.size()<<'\n';
for(int i=0;i<ap.size() && i< 1000; ++i){
fout<<ap[i]<<' ';
}
return 0;
}