Cod sursa(job #1518170)

Utilizator nnnmmmcioltan alex nnnmmm Data 5 noiembrie 2015 17:47:49
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MOD 666013
bool poz[2000001];
char s1[2000001],s2[2000001];
char get_hash(char ch)
{
 if(ch>='A' && ch<='Z')
    ch=ch-'A'+1;
 else
    if(ch>='a' && ch<='z')
       ch=ch-'a'+27;
    else
       ch=ch-'0'+53;
 return ch;
}
int main()
{
 freopen("strmatch.in","r",stdin);
 freopen("strmatch.out","w",stdout);
 scanf("%s %s ",s1,s2);
 int n1=strlen(s1),n2=strlen(s2),H1=0,H2=0;
 int put=1;
 for(int i=0;i<n1;i++)
     {
      s1[i]=get_hash(s1[i]);
      H1=(H1*63+s1[i])%MOD;
      if(i!=n1-1)
         {
          put*=63;
          put%=MOD;
         }
     }
 if(n1>n2)
    {
     printf("0\n");
     return 0;
    }
 put=1;
 for(int i=0;i<n1;i++)
     {
      s2[i]=get_hash(s2[i]);
      //H2=(H2*73+s2[i])%MOD;
      H2=(H2*63+s2[i])%MOD;
      if(i!=n1-1)
         {
          put*=63;
          put%=MOD;
         }
     }
 int rasp=0;
 if(H1==H2)
    {
     rasp++;
     poz[0]=true;
    }
 for(int i=n1;i<n2;i++)
     {
      s2[i]=get_hash(s2[i]);
      H2=((H2-(s2[i-n1]*put)%MOD+MOD)*63+s2[i])%MOD;
      //H2=((H2-(s2[i-n1]*63)%MOD)*63+s2[i])%MOD;
      if(H2==H1)
         {
          rasp++;
          poz[i-n1+1]=true;
         }
     }
 printf("%d\n",rasp);
 rasp=0;
 for(int i=0;i<=n2 && rasp<1000;i++)
     {
      if(poz[i])
         printf("%d ",i),rasp++;
     }
 fclose(stdin);
 fclose(stdout);
return 0;
}