Pagini recente » Cod sursa (job #1370122) | Cod sursa (job #2600509) | Cod sursa (job #2382266) | Cod sursa (job #1414159) | Cod sursa (job #2497760)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const long long mod=1000000007;
string a;
string b;
long long val,puteri[2000001],baza,h,ans,sol[2000001],lg;
int main()
{
fin>>a>>b;
baza=127;
puteri[0]=1;
for(int i=1;i<=a.size()+1;i++)
puteri[i]=(puteri[i-1]*baza)%mod;
for(int i=0;i<a.size();i++)
{
int x=a.size()-i-1;
val=(val+(puteri[x]*a[i])%mod)%mod;
}
for(int i=0;i<a.size();i++)
{
int x=a.size()-i-1;
h=(h+(puteri[x]*b[i])%mod)%mod;
}
if(h==val)
{
ans++;
sol[++lg]=0;
}
for(int i=1;i<b.size();i++)
{
if(i+a.size()-1>=b.size())
break;
h=(((h-puteri[a.size()-1]*b[i-1])*baza)%mod+b[i+a.size()-1])%mod;
if(h<0)
h+=mod;
/*if(i==474)
fout<<h<<" "<<val<<" ";*/
if(h==val)
{
ans++;
sol[++lg]=i;
}
}
fout<<ans<<'\n';
for(int i=1;i<=min(ans,1000LL);i++)
fout<<sol[i]<<" ";
return 0;
}