Pagini recente » Monitorul de evaluare | Cod sursa (job #1447996) | Istoria paginii runda/baaabaa | Cod sursa (job #1428132) | Cod sursa (job #2789470)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
long long rasp[1005];
string a,b;
void subsir()
{
long long nr=0;
long long n=a.size();
long long pp,c=0,cod=0,p=1;
long long mod=100007;
for(long long i=n-1; i>=0; i--)
{
cod+=(a[i]-'A')*p;
cod%=mod;
p*=26;
p%=mod;
if(i==1)pp=p;
}
long long m=b.size();
p=1;
if(n>m)
{
fout<<0;
return;
}
for(long long i=n-1; i>=0; i--)
{
c+=(b[i]-'A')*p;
cod%=mod;
p*=26;
p%=mod;
}
if(c==cod)
{
long long i=0;
while(a[i]==b[i]&&i<n)
{
i++;
}
if(i==n)
{
rasp[++nr]=0;
}
}
for(long long i=n; i<m; i++)
{
c+=mod;
c-=(b[i-n]-'A')*pp;
c%=mod;
c*=26;
c%=mod;
c+=b[i]-'A';
c%=mod;
if(c==cod)
{
long long j=0;
long long k=i-n+1;
while(a[j]==b[k]&&j<n)
{
j++;
k++;
}
if(j==n)
{
rasp[++nr]=i-n+1;
if(nr==1000)break;
}
}
}
fout<<nr<<'\n';
for(long long i=1; i<=nr; i++)fout<<rasp[i]<<" ";
}
int main()
{
fin>>a;
fin.get();
fin>>b;
subsir();
return 0;
}