Pagini recente » Cod sursa (job #820199) | Cod sursa (job #820201) | Cod sursa (job #2397150) | Cod sursa (job #820197) | Cod sursa (job #820189)
Cod sursa(job #820189)
#include<fstream>
#include<string.h>
#define mod 666013
#define mod2 100107
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char A[2000001], B[2000001];
int poz[1002];
int main()
{ int s1,s2,s21,s22,p1,p2,p21,p22,n=0,pf,pf2,i;
fin.getline(A,2000001);
fin.getline(B,2000001);
p1=1;p2=1;s1=0;s2=0;
i=1;
pf=1;pf2=1;
while(i<strlen(A))
{
pf=(pf*75)%mod;
pf2=(pf2*75)%mod2;
i++;
}
for(i=strlen(A)-1;i>=0;i--)
{
s1=(s1+(int)(A[i]-'0')*p1)%mod;
s2=(s2+(int)(A[i]-'0')*p2)%mod2;
p1=(p1*75)%mod;
p2=(p2*75)%mod2;
}
if(strlen(A)<=strlen(B))
{
p21=1;p22=1;s21=0;s22=0;
for(i=strlen(A)-1;i>=0;i--)
{
s21=(s21+(B[i]-'0')*p21)%mod;
s22=(s22+(B[i]-'0')*p22)%mod2;
p21=(p21*75)%mod;
p22=(p22*75)%mod2;
}
}
if(s21==s1&&s22==s2){n++; poz[n]=0;}
for(i=strlen(A);i<strlen(B);i++)
{
s21=((s21-(B[i-strlen(A)]-'0')*pf%mod+mod)%mod*75%mod+B[i]-'0')%mod;
s22=((s22-(B[i-strlen(A)]-'0')*pf2%mod2+mod2)%mod2*75%mod2+B[i]-'0')%mod2;
if(s21==s1&&s22==s2)if(n<1000)poz[++n]=i-strlen(A)+1;
else n++;
}
fout<<n<<"\n";
for(i=1;i<=n&&i<=1000;i++)
fout<<poz[i]<<" ";
return 0;
}