Pagini recente » Cod sursa (job #791821) | Cod sursa (job #1645358) | Cod sursa (job #1381624) | Cod sursa (job #2792479) | Cod sursa (job #1514303)
#include<cstdio>
#include<cstring>
# define MOD 666013
using namespace std;
int i,j,n,k,m=0,x,y,c=0,s=0,v[1001];
char s1[2000001],s2[2000001];
FILE *in,*out;
int main ()
{
in=fopen("strmatch.in","r");
out=fopen("strmatch.out","w");
fscanf(in,"%s %s",&s2,&s1);
n=strlen(s1);
k=strlen(s2);
for(i=0;i<k;i++)
{
//numarul caracteristic sirului de cautat
if(s2[i]>='A' && s2[i]<='Z')
x=s2[i]-'A';
else if(s2[i]>='a' && s2[i]<='z')
x=26+s2[i]-'a';
else
x=52+s2[i]-'0';
c*=62;
c%=MOD;
c+=x;
//numarul caracteristic primului subsir de lungime k din sirul in care caut
if(s1[i]>='A' && s1[i]<='Z')
x=s1[i]-'A';
else if(s1[i]>='a' && s1[i]<='z')
x=26+s1[i]-'a';
else
x=52+s1[i]-'0';
s*=62;
s%=MOD;
s+=x;
}
if(s==c)
{
int pp=1;
for(j=0;j<k && pp==1;j++)
if(s2[j]!=s1[i-k+j])
pp=0;
if(pp==1)
{
m++;
v[m]=i-k;
}
}
for(i=k;i<n && m<1000;i++)
{
if(s1[i]>='A' && s1[i]<='Z')
x=s1[i]-'A';
else if(s1[i]>='a' && s1[i]<='z')
x=26+s1[i]-'a';
else
x=52+s1[i]-'0';
//elimin ultimul caracter de ordin prea mic pentru numarul nou creat
if(s1[i-k]>='A' && s1[i-k]<='Z')
y=s1[i-k]-'A';
else if(s1[i-k]>='a' && s1[i-k]<='z')
y=26+s1[i-k]-'a';
else
y=52+s1[i-k]-'0';
for(j=1;j<k;j++)
{
y*=62;
y%=MOD;
}
s-=y;
s*=62;
s%=MOD;
s+=x;
/*if(s==c)
{
int pp=1;
for(j=0;j<k && pp==1;j++)
if(s2[j]!=s1[i-k+j+1])
pp=0;
if(pp==1)
{
m++;
v[m]=i-k+1;
}
}*/
}
fprintf(out,"%d\n",m);
for(i=1;i<=m;i++)
fprintf(out,"%d ",v[i]);
return 0;
}