Pagini recente » Cod sursa (job #630896) | Cod sursa (job #913985) | Cod sursa (job #1198925) | Cod sursa (job #298680) | Cod sursa (job #1982365)
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MODA=666013;
const int MODB=1000003;
const int BASE=62;
char sircmp[2000005];
char sirm[2000005];
int rez [1005];
int transf(char x){
if(x>='a' && x<='z')
return 10 + x - 'a';
if(x>='A' && x<='Z')
return 11 + 'z' - 'a' + x- 'A';
return x-'0';
}
int main()
{
FILE*fin,*fout;
int i,n,j,m,codma,codmb,codla,codlb;
int uelema,uelemb;
fin=fopen("strmatch.in","r");
fgets(sircmp,2000006,fin);
fgets(sirm,2000006,fin);
m=strlen(sircmp)-1;
n=strlen(sirm)-1;
codma=0;
codmb=0;
int m62a=1,m62b=1;
for(int p=0;p<m-1;p++){
m62a=(m62a*62)%MODA;
m62b=(m62b*62)%MODB;
}
for(i=0;i<m;i++){
codma=(codma*BASE%MODA + transf(sircmp[i]))%MODA;
codmb=(codmb*BASE%MODB+ transf(sircmp[i]))%MODB;
}
j=0;
codla=0;
codlb=0;
fout=fopen("strmatch.out","w");
for(i=0;i<m && i<n;i++){
codla=((codla*BASE)%MODA + transf(sirm[i]))%MODA;
codlb=((codlb*BASE)%MODB + transf(sirm[i]))%MODB;
}
if(codla==codma && codlb==codmb)
rez[j++]=0;
for(i=m;i<n;i++){
int lit=transf(sirm[i-m]);
uelema=(lit*m62a)%MODA;
uelemb=(lit*m62b)%MODB;
codla=((((codla+MODA-uelema)%MODA)*62)%MODA+transf(sirm[i]))%MODA;
codlb=((((codlb+MODB-uelemb)%MODB)*62)%MODB+transf(sirm[i]))%MODB;
if(codla==codma && codlb==codmb){
if(j<=1000)
rez[j++]=i-m+1;
else
j++;
}
}
fprintf(fout,"%d\n",j);
if(j>1000)
j=1000;
for(i=0;i<j;i++)
fprintf(fout,"%d ",rez[i]);
return 0;
}