Pagini recente » Cod sursa (job #590046) | Cod sursa (job #1340134) | Cod sursa (job #494683) | Cod sursa (job #181366) | Cod sursa (job #3274485)
#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];
queue <int> ans;
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.push(i-1), j++;
if(j == 999) break;
}
fout << j << "\n";
while(!ans.empty()){
fout << ans.front() << " ";
ans.pop();
}
}