Pagini recente » Borderou de evaluare (job #2707556) | Cod sursa (job #3001833) | Cod sursa (job #2547297) | Borderou de evaluare (job #1787946) | Cod sursa (job #3274478)
#include <bits/stdc++.h>
#define int long long
#define DIM 2000001
#define mod 1000000009
#define base 1087
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string s;
int n, target, len;
int hash_[DIM], p[DIM], ans[DIM];
int i, j;
void precalc_pow(){
p[1] = base;
int s0 = s.size();
for(int i = 2; i <= s0; i++)
p[i] = (p[i-1] * base) % mod;
}
void precalc_hash(){
int s0 = s.size();
for(int j = 1; j <= s0; j++)
hash_[j] = ((hash_[j-1] * base) % mod + s[j-1]) % mod;
}
int get_hash(int l, int r){
int ret = hash_[r] - (hash_[l-1] * p[r-l+1]) % mod;
return (ret + mod) % mod;
}
int32_t main(){
fin >> s;
precalc_pow();
n -= s.size();
len = s.size();
precalc_hash();
target = get_hash(1, len);
fin >> s;
precalc_pow();
n += (s.size() + 1);
precalc_hash();
for(i = 1; i <= n; i++)
if(target == get_hash(i, i + len - 1))
ans[++j] = i-1;
fout << j << "\n";
for(i = 1; i <= j && i <= 1000; i++)
fout << ans[i] << " ";
}