Pagini recente » Cod sursa (job #1371682) | Cod sursa (job #2398280) | Cod sursa (job #2635891) | Cod sursa (job #1223201) | Cod sursa (job #2084109)
#include <iostream>
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string a,b;
long long nr,act,p[2000005],n,m,sp[2000005];
vector<int> sol;
int main()
{
in>>a>>b;
n=a.size();
m=b.size();
if(n>m)
{
out<<0;
return 0;
}
p[0]=1;
act=0;
nr=0;
for(int i=1;i<m;++i)
p[i]=p[i-1]*97;
sp[0]=a[0]-'A'+1;;
for(int i=1;i<m;++i)
sp[i]=sp[i-1]+(b[i]-'A'+1)*p[i];
for(int i=0;i<n;++i)
nr=nr+(a[i]-'A'+1)*p[i];
nr=nr*p[m-n];
if(nr==sp[n])sol.pb(0);
for(int i=n;i<m;++i)
if((sp[i]-sp[i-n])*p[m-1-i]==nr)sol.pb(i-n);
out<<sol.size()<<'\n';
while(sol.size()>1000)sol.pop_back();
for(auto i:sol)out<<i+1<<" ";
return 0;
}