Cod sursa(job #1488920)

Utilizator vrabievictorvictor vrabie vrabievictor Data 20 septembrie 2015 10:02:46
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include<cstdio>
#include<cstring>
#define b1 73
#define b2 73
#define mod1 100007
#define mod2 100003

using namespace std;

long long hasha,hashb,hash1,hash2,p1,p2,i,n,mb;
int m[1090],nr=0;

char a[2000009],b[2000009];

int min(int a,int b)
{
    if (a<b) return a;
    return b;
}

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s %s",&a,&b);
    p1=p2=1;hasha=hashb=0;n=strlen(a);mb=strlen(b);
    for (i=0;i<n;i++)
    {
      hasha=(hasha*b1+a[i])%mod1;
      hashb=(hashb*b2+a[i])%mod2;
    }
    for (i=1;i<n;i++)
        p1=(p1*b1)%mod1,p2=(p2*b2)%mod2;
        hash1=hash2=0;
   for (i=0;i<n;i++)
   {
       hash1=(hash1*b1+b[i])%mod1;
       hash2=(hash2*b2+b[i])%mod2;
   }
   if (hasha==hash1 && hashb==hash2) m[nr++]=0;
   for (i=n;i<mb;i++)
   {
       hash1=(((hash1-p1*b[i-n])%mod1+mod1)*b1+b[i])%mod1;
       hash2=(((hash2-p2*b[i-n])%mod2+mod2)*b2+b[i])%mod2;
       if (hasha==hash1 && hashb==hash2  )
       {
          nr++;
          if (nr<1001) m[nr]=i-n+1;
       }
   }
   printf("%d\n",nr);
   for (i=1;i<=min(nr,1000);i++)
    printf("%d ",m[i]);

    return 0;
}