Pagini recente » Cod sursa (job #1140950) | Cod sursa (job #365883) | Cod sursa (job #854516) | Cod sursa (job #1100057) | Cod sursa (job #3243048)
#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=53;
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;
int cnt=0;
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)
{
if(cnt<1000)
pozitii.push_back(i-1);
++cnt;
}
}
cout<<cnt<<'\n';
for(auto x:pozitii)
cout<<x<<' ';
return 0;
}