Pagini recente » Statistici Emanuel Soto Ortega (cegax) | Istoria paginii utilizator/nottherealgeorge | Cod sursa (job #2304964) | Cod sursa (job #890764) | Cod sursa (job #3243043)
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
//ifstream cin("strmatch.in");
//ofstream cout("strmatch.out");
string a, b;
cin>>a>>b;
int n=a.size(), m=b.size();
a=" "+a;
b=" "+b;
const int MOD=1e9+9;
const int base=31;
vector<long long> pow(max(n, m)+1);
pow[1]=1;
for(int i=2; i<(int)pow.size(); i++)
pow[i]=(pow[i-1]*base)%MOD;
vector<long long> h(m+1, 0);
for(int i=1; i<=m; i++)
h[i]=(h[i-1]+(b[i]-'A'+1)*pow[i])%MOD;
long long hash_a=0;
for(int i=1; i<=n; i++)
hash_a=(hash_a+(a[i]-'A'+1)*pow[i])%MOD;
vector<int> pozitii;
for(int i=1; i+n-1<=m; i++)
{
long long cur_h = (h[i+n-1]+MOD-h[i-1])%MOD;
if(cur_h == hash_a * pow[i] % MOD)
pozitii.push_back(i-1);
}
cout<<pozitii.size()<<'\n';
for(int i=0; i<(int)pozitii.size() && i<1000; i++)
cout<<pozitii[i]<<' ';
return 0;
}