Pagini recente » Cod sursa (job #2397705) | Cod sursa (job #2397700) | Cod sursa (job #2397239) | Cod sursa (job #820203) | Cod sursa (job #820199)
Cod sursa(job #820199)
#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,p21,p22,n=0,pf,pf2,i;
fin.getline(A,2000001);
fin.getline(B,2000001);
s1=0;s2=0;i=1;
pf=1;pf2=1;
p21=1;p22=1;s21=0;s22=0;
for(i=1;i<strlen(A);i++)
{
s1=( s1*p21 + (A[i]-'0') )%mod;
s2=( s2*p22 + (A[i]-'0') )%mod2;
s21=( s21*p21 +(B[i]-'0') )%mod;
s22=( s22*p22 + (B[i]-'0') )%mod2;
p21=(p21*75)%mod;
p22=(p22*75)%mod2;
if(i){
pf=(pf*75)%mod;
pf2=(pf2*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 ) * 75 % mod + B[i] - '0' ) % mod;
s22=( ( s22 - ( B [ i - strlen(A) ] - '0' ) * pf2 % 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;
}