Pagini recente » Cod sursa (job #387400) | Cod sursa (job #1168827) | Cod sursa (job #3170018) | Istoria paginii schimbare-borland/argumentatie | Cod sursa (job #3251930)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int base = 127;
const int nmax = 2e6+10;
const int MOD = 1e9+7;
string s1,s2;
vector<long long int> hash_(nmax,0),base_power(nmax,0);
vector<int> ans;
long long n,m,s2_hash,ans_value;
void precalculations(){
base_power[0] = 1;
for(int i = 1; i <=nmax; i++){
base_power[i] = (base_power[i-1]*base)%MOD;
}
s2_hash = 0;
for(int i = 0; i <m; i++){
s2_hash *= base;
s2_hash += s2[i]-'0';
s2_hash %= MOD;
}
for(int i = 1; i < n; i++){
hash_[i+1] = hash_[i];
hash_[i+1] *= base;
hash_[i+1] += s1[i]-'0';
hash_[i+1] %= MOD;
}
}
void solve(){
for(int i = m; i <=n; i++){
long long int hash_dr = hash_[i];
long long int hash_st = hash_[i-m];
hash_st = (hash_st * base_power[m])%MOD;
long long int hash_aux = (hash_dr-hash_st + MOD)%MOD;
if(hash_aux == s2_hash){
ans_value++;
if(ans_value <= 1000){
ans.push_back(i-m);
}
}
}
}
int main(){
fin >> s2 >> s1;
n = (int) s1.length();
m = (int) s2.length();
precalculations();
solve();
fout << ans_value << '\n';
for(auto x : ans){fout << x << " ";}
return 0;
}