Cod sursa(job #228505)

Utilizator marcelcodreaCodrea Marcel marcelcodrea Data 7 decembrie 2008 13:34:16
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <stdio.h>
#include <string.h>

#define MAXN 2000001

#define P 73
#define mod1 100007
#define mod2 100021

char a[MAXN], b[MAXN];
int h1A,h2A,h1B,h2B;
int P1,P2;
int nr;
int k;
int la,lb;
char poz[MAXN];




int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    scanf("%s %s",&a,&b);
    la = strlen(a);
    lb = strlen(b);

    P1 = P2 = 1;
    for(int i = 0; i < la; i++)
     {
         h1A = (h1A * P + a[i]) % mod1;
         h2A = (h2A * P + a[i]) % mod2;
         h1B = (h1B * P + b[i]) % mod1;
         h2B = (h2B * P + b[i]) % mod2;
         if (i != 0)
           {
               P1 = (P1 * P) % mod1;
               P2 = (P2 * P) % mod2;
           }
     }
    for(int i = 0; i < lb-la; i++)
     {
         if ((h1A == h1B) && (h2A == h2B))
           {
             k++;
             poz[i] = 1;
           }
         h1B = ((h1B - (P1 * b[i]) % mod1 + mod1) * P + b[i+la]) % mod1;
         h2B = ((h2B - (P2 * b[i]) % mod2 + mod2) * P + b[i+la]) % mod2;
     }

     printf("%d \n",k);
     for(int i = 0;  ; i++)
      {
          if (poz[i]) printf("%d ",i);
          nr+= poz[i];
          if (nr == 1000) break;
          if (nr == k) break;
      }




    return 0;
}