Pagini recente » Cod sursa (job #1122235) | Cod sursa (job #1098742) | Cod sursa (job #2550385) | Cod sursa (job #2143152) | Cod sursa (job #812699)
Cod sursa(job #812699)
#include<fstream>
#include<string.h>
#include<ctype.h>
#define mod 666013
#define mod2 1000122
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,p1,p2,p21,p22,n=0,pf,pf2,i;
fin.getline(A,2000001);
fin.getline(B,2000001);
strlwr(A);
strlwr(B);
p1=1;p2=1;s1=0;s2=0;
i=1;
pf=1;pf2=1;
while(i<strlen(A)){pf=(pf*26)%mod;pf2=(pf2*26)%mod2;i++;}
for(i=strlen(A)-1;i>=0;i--)
{
s1=(s1+(int)(A[i]-'a')*p1)%mod;
s2=(s2+(int)(A[i]-'a')*p2)%mod2;
p1=(p1*26)%mod;
p2=(p2*26)%mod2;
}
if(strlen(A)<=strlen(B))
{
p21=1;p22=1;s21=0;s22=0;
for(i=strlen(A)-1;i>=0;i--)
{
s21=(s21+(B[i]-'a')*p21)%mod;
s22=(s22+(B[i]-'a')*p22)%mod2;
p21=(p21*26)%mod;
p22=(p22*26)%mod2;
}
}
if(s21==s1&&s22==s2){n++; poz[n]=0;}
for(i=strlen(A);i<strlen(B);i++)
{
s21=((s21-(B[i-strlen(A)]-'a')*pf)*26%mod+B[i]-'a')%mod;
s22=((s22-(B[i-strlen(A)]-'a')*pf2)*26%mod2+B[i]-'a')%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;
}