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