Cod sursa(job #183380)

Utilizator pandaemonAndrei Popescu pandaemon Data 22 aprilie 2008 00:22:09
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include<stdio.h>
#include<string.h>
#include<iostream.h>

#define SMAX 2000005

#define DIV1 100007
#define DIV2 100021
#define B 73

char sub[SMAX],s[SMAX];

long n_sub, n_s, i, cmp1,cmp2, hash1,hash2, b1=1,b2=1;

int poz[1001];

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

  scanf("%s %s", sub, s);

  n_sub = strlen(sub);   n_s = strlen(s);


  if(n_sub > n_s)  { printf("0\n"); return 0; }

  n_s = n_s - n_sub + 2 ;
		   // verific daca exista subsecventa cu deplasamentul i-1

  for(i=0; i<n_sub; i++)
  {
    cmp1= (cmp1*B + sub[i]) % DIV1;
    cmp2= (cmp2*B + sub[i]) % DIV2;

    hash1= (hash1*B + s[i]) % DIV1;
    hash2= (hash2*B + s[i]) % DIV2;    if(i!=0) { b1=(b1*B) % DIV1;
						  b2=(b2*B) % DIV2; }
  }


  for(i=n_sub; i<=n_s && poz[0]<=1000; i++)
  {
    if(hash1==cmp1 && hash2==cmp2)  poz[++poz[0]] = i - n_sub;

    hash1= ( (hash1 - (s[i-n_sub]*b1) % DIV1 + DIV1) *B + s[i] ) % DIV1;
    hash2= ( (hash2 - (s[i-n_sub]*b2) % DIV2 + DIV2) *B + s[i] ) % DIV2;
  }


  printf("%d\n",poz[0]);

  for(i=1; i<=poz[0]; i++)
    printf("%d ",poz[i]);


  printf("\n"); return 0; }