Cod sursa(job #629470)

Utilizator sory1806Sandu Sorina-Gabriela sory1806 Data 3 noiembrie 2011 13:53:13
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <math.h>

using namespace std;

#define MAX_LG 2000010
#define MAX_P 1000000000039
char s1[MAX_LG], s2[MAX_LG];
long long B, Bn, ns1, ns2, nr, rez[1001], base, hash;
char symb[256];


long long next_prime (long long x) {
  int ok;
  while (1) {
    ok = 1;
    for (int i = 2; i <= sqrt (x); i ++)
      if (x % i == 0) {
	ok = 0;
	break;
      }
    if (ok)
      return x;
    x ++;
  }
}

long long first_hash (char *s, int p, int u) {
  long long pw = 1;
  long long rez = 0;

  for (int i = u; i >= p; i --) {
    rez = (rez + (s[i] * pw) % MAX_P ) % MAX_P;
    pw = (pw * B) % MAX_P;
  }

  Bn = pw / B;
  return rez;
}

long long next_hash (char *s, int old_hash, int p, int u) {
  long long new_hash;
  new_hash = (old_hash - (s[p-1] * Bn) % MAX_P) % MAX_P;
  if (new_hash < 0)
    new_hash += MAX_P;

  new_hash = (new_hash * B) % MAX_P;
  new_hash = (new_hash + s[u]) % MAX_P;
}

long long det_base (char *s) {
  long long nrsymb = 0;

  for (int i = 0; s[i]; i ++) 
    if (!symb[s[i]]) {
      nrsymb ++;
      symb[s[i]] = 1;
    }

  return nrsymb;
}


int main () {

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

  fgets (s1, MAX_LG, stdin);
  ns1 = strlen (s1) - 1;
  s1[ns1] = 0;
  fgets (s2, MAX_LG, stdin);
  ns2 = strlen (s2) - 1;
  s2[ns2] = 0;

  puts (s1);
  puts (s2);

  B = next_prime (det_base (s2));

  base = first_hash (s1, 0, ns1- 1);
  hash = first_hash (s2, 5, ns1 + 4);

  for (int i = 0; i < ns2 - ns1; i ++)
    if (hash == base && strncmp (s1, s2 + i, ns1) == 0) 
      if (nr < 1000)
	rez[nr++] = i;

  printf ("%lld\n", nr);
  for (int i = 0; i < nr; i ++)
    printf ("%lld ", rez[i]);



  return 0;
}