Pagini recente » Cod sursa (job #2190468) | Cod sursa (job #2219954) | Cod sursa (job #2068118) | Cod sursa (job #116688) | Cod sursa (job #1991579)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int chtoiaA0(char ch)
{
if(('0'<=ch)&&(ch<='9'))
{
return ch-'0'+1;
}
if(('a'<=ch)&&(ch<='z'))
{
return ch-'a'+11;
}
else
return ch-'A'+37;
}
int main()
{
string a,b;
vector<int> x;
int R1=0,R2=0,B=63;
int pow1=1,pow2=1;
int mod1=666013,mod2=666019;
fin>>a;
fin>>b;
int asize=a.size(),bsize=b.size();
int mare1=1LL*mod1*(B+1), mare2=mod2*(B+1);
for(int i=0;i<asize;i++)
{
R1=(R1*1LL*B+(chtoiaA0(a[i])))%mod1;
R2=(R2*1LL*B+(chtoiaA0(a[i])))%mod2;
}
int r1=0,r2=0, ans=0;
for(int i=0;i<bsize;i++)
{
if(i<asize-1)
{
pow1=(pow1*B)%mod1;
pow2=(1LL*pow2*B)%mod2;
}
if(i>=asize)
{
r1=(r1-pow1*(chtoiaA0(b[i-asize]))+mare1)%mod1;
r2=(r2-pow2*(chtoiaA0(b[i-asize]))+mare2)%mod2;
}
r1=(r1*B+(chtoiaA0(b[i])))%mod1;
r2=(r2*B+(chtoiaA0(b[i])))%mod2;
if(i>=asize-1)
{
if(R1==r1 && R2==r2)
{
ans++;
if(x.size()<1000)
x.push_back(i-asize);
}
}
}
fout<<ans<<'\n';
for(int i:x)
{
fout<<i+1<<" ";
}
return 0;
}