aiuto in teoria riguardo a prefix_suffix_set

0

Ho trovato questa domanda su codility.com, ma non capisco la domanda. Puoi aiutarmi a capire cosa vogliono? Sono più interessato alla teoria di un codice.

Viene fornito un array A non indicizzato vuoto vuoto A costituito da N numeri interi. Un prefisso_suffix_set è una coppia di indici (P, S) tale che 0 ≤ P, S < N e tale che:

  • ogni valore che si verifica nella sequenza A [0], A [1], ..., A [P] si verifica anche nella sequenza A [S], A [S + 1], ..., A [N - 1],
  • ogni valore che si verifica nella sequenza A [S], A [S + 1], ..., A [N - 1] si verifica anche nella sequenza A [0], A [1], ... , A [P].

L'obiettivo è calcolare il numero di prefisso_suffix_sets nell'array. Ad esempio, considera l'array A tale che:

  • A [0] = 3
  • A [1] = 5
  • A [2] = 7
  • A [3] = 3
  • A [4] = 3
  • A [5] = 5

Ci sono esattamente quattordici prefix_suffix_sets: (1, 4), (1, 3), (2, 2), (2, 1), (2, 0), (3, 2), (3, 1) , (3, 0), (4, 2), (4, 1), (4, 0), (5, 2), (5, 1), (5, 0).

Scrivi una funzione:

  • funzione soluzione (A);

che, dato un array A non indicizzato zero vuoto di N interi, restituisce il numero di prefix_suffix_sets.

    
posta user2766731 11.09.2013 - 01:00
fonte

1 risposta

1

Se leggo le cose correttamente:

(1,4) indica la parte dell'array

i   0 1 2 3 4 5
A   3 5 7 3 3 5
p/s p p     s s

In questo set, tutto ciò che si verifica in A[0..1] si verifica anche in A[4..5] .

L'insieme non riguarda la molteplicità di un numero (1,3) mostra:

i   0 1 2 3 4 5
A   3 5 7 3 3 5
p/s p p   s s s

3 si verifica due volte nel set di "s" e una volta nel set di "p".

Questi possono essere sovrapposti (2,2)

i   0 1 2 3 4 5
A   3 5 7 3 3 5
p   p p p 
        s s s s

e (2,1)

i   0 1 2 3 4 5
A   3 5 7 3 3 5
p   p p p 
      s s s s s

La domanda sta chiedendo "quanti di questi accoppiamenti (suffisso e prefisso) esistono dove l'insieme di numeri nella parte prefisso dell'array corrisponde all'insieme di numeri nella parte suffisso dell'array?"

    
risposta data 11.09.2013 - 01:33
fonte

Leggi altre domande sui tag