Pagini recente » Cod sursa (job #2742594) | Cod sursa (job #2115988) | Cod sursa (job #2591960) | Cod sursa (job #396894) | Cod sursa (job #1982239)
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MODA=100007;
const int MODB=100003;
const int BASE=74;
char sircmp[2000000];
char sirm[2000000];
int rez [1001];
int transf(int x){
return x-'0';
}
int main()
{
FILE*fin,*fout;
int i,n,j,m,codma,codmb,codla,codlb;
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 mBASEa=1,mBASEb=1;
for(int p=0;p<m-1;p++){
mBASEa=(mBASEa*BASE)%MODA;
mBASEb=(mBASEb*BASE)%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 + transf(sirm[i]))%MODA;
codlb=(codlb*BASE + transf(sirm[i]))%MODB;
}
if(codla==codma && codlb==codmb)
rez[j++]=0;
for(i=m;i<n;i++){
codla=(((codla+MODA-transf(sirm[i-m])*mBASEa+MODA)%MODA)*BASE+ transf(sirm[i]))%MODA;
codlb=(((codlb+MODB-transf(sirm[i-m])*mBASEb+MODB)%MODB)*BASE+ transf(sirm[i]))%MODB;
if(codla==codma && codlb==codmb){
if(j<=1000)
rez[j++]=i-m+1;
else
j++;
}
}
fprintf(fout,"%lld\n",j);
if(j>1000)
j=1000;
for(i=0;i<j;i++)
fprintf(fout,"%lld ",rez[i]);
return 0;
}