Pagini recente » Cod sursa (job #1923059) | Cod sursa (job #2506877) | Cod sursa (job #1950649) | Cod sursa (job #1976364) | Cod sursa (job #2626447)
#include <bits/stdc++.h>
using namespace std;
ifstream r("strmatch.in");
ofstream w("strmatch.out");
vector<int>f;
int h[2000002];
const int base=113, mod=1130011;
int main()
{
string a, b;
r>>a>>b;
int n=a.size(), m=b.size();
long long has=0, inm=base;
for(int i=n-1; i>=0; i--)
{
has+=a[i]*inm;
has%=mod;
inm*=base;
inm%=mod;
}
inm=base;
for(int i=m-1; i>=0; i--)
{
h[i]=h[i+1]+b[i]*inm;
h[i]%=mod;
inm*=base;
inm%=mod;
}
for(int i=m-n; i>=0; i--)
{
long long rez;
if(h[i]>h[i+n])
{
rez=h[i]-h[i+n];
}
else
{
rez=h[i]+mod-h[i+n];
}
if(rez==has)
{
f.push_back(i);
}
has*=base;
has%=mod;
}
w<<f.size()<<"\n";
for(int i=f.size()-1; i>=0; i--)
{
w<<f[i]<<" ";
}
return 0;
}