Pagini recente » Cod sursa (job #275524) | Cod sursa (job #1744501) | Cod sursa (job #1967042) | Cod sursa (job #1082983) | Cod sursa (job #2207369)
#include <fstream>
#include <cstring>
#define p1 90917
#define p2 666013
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
inline int scif(char ch)
{
if(ch>='0' && ch<='9')
return ch - '0';
if(ch >= 'A' and ch <= 'Z')
return ch - 'A' + 10;
return ch - 'a' + 36;
}
char ch1[2000000],ch2[2000000];
int v[1001];
int main()
{
long long nr=0,p=1;
int l,i,r1,r2,rr1,rr2;
int k;
in.get(ch1,2000000);
in.get();
in.get(ch2,2000000);
k=strlen(ch1);
l=strlen(ch2);
for(i=0;i<k;i++)
{
nr+=p*(scif(ch1[i]));
p*=62;
p%=p1;
}
r1=nr%p1;
p=1;
nr=0;
int q=0;
for(i=0;i<k;i++)
{
nr+=p*(scif(ch1[i]));
p*=62;
p%=p2;
}
r2=nr%p2;
long long n,z;
p=1;
for(i=0;i<k;i++)
{
n+=p*(scif(ch2[i]));
z=p;
p*=62;
p%=p1;
}
rr1=n%p1;
n=0;
p=1;
long long z2,cn;
for(i=0;i<k;i++)
{
n+=p*(scif(ch2[i]));
z2=p;
p*=62;
p%=p2;
}
rr2=n%p2;
cn=n;
if(r1==rr1 && r2==rr2)
{
q++;
v[q]=i;
}
for(i=1;i<l-k;i++)
{
n+=p1;
n-=((scif(ch2[i-1])*z)%p1);
n=(62*n)%p1;
n=(n+scif(ch2[i+k]))%p1;
rr1=n%p1;
cn+=p2;
cn-=((scif(ch2[i-1])*z)%p2);
cn=(62*cn)%p2;
cn=(n+scif(ch2[i+k]))%p2;
rr2=cn%p2;
if(r1==rr1 && r2==rr2)
{
q++;
v[q]=i;
}
}
out<<q<<'\n';
if(q>1000)
q=1000;
for(i=1;i<=q;i++)
out<<v[i]<<" ";
return 0;
}