Cod sursa(job #1517845)

Utilizator nnnmmmcioltan alex nnnmmm Data 4 noiembrie 2015 22:00:11
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include<cstdio>
#include<cstring>
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=n1-1;i>=0;i--)
     {
      s1[i]=get_hash(s1[i]);
      H1=(H1+s1[i]*put)%666013;
      if(i!=0)
         {
          put*=63;
          put%=666013;
         }
     }
 if(n1>n2)
    {
     printf("0\n");
     return 0;
    }
 put=1;
 for(int i=n1-1;i>=0;i--)
     {
      s2[i]=get_hash(s2[i]);
      //H2=(H2*73+s2[i])%666013;
      H2=(H2+s2[i]*put)%666013;
      if(i!=0)
         {
          put*=63;
          put%=666013;
         }
     }
 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)%666013)*63+s2[i])%666013;
      if(H2==H1)
         {
          rasp++;
          poz[i-n1+1]=true;
         }
     }
 printf("%d\n",rasp);
 for(int i=0;i<=n2 && i<1000;i++)
     {
      if(poz[i])
         printf("%d ",i);
     }
 fclose(stdin);
 fclose(stdout);
return 0;
}