Pagini recente » Cod sursa (job #86830) | Cod sursa (job #2146742) | Cod sursa (job #486783) | Cod sursa (job #3212969) | Cod sursa (job #1982349)
#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,2000001,fin);
fgets(sirm,2000001,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 + transf(sircmp[i]))%MODA;
codmb=(codmb*BASE + 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++){
uelema=(transf(sirm[m-i])*m62a)%MODA;
uelemb=(transf(sirm[m-i])*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;
}