Trova il numero di subarray ripetuto in una matrice

Question

C'è una matrice indicizzata da 0-n (cioè size = n) contenente elementi da 0-m dove m < n (supponiamo m è 100 o 1000 volte minore di n ie m è molto minore di n) , quindi molti degli elementi o sottoarray devono essere ripetuti e dobbiamo trovare il numero di tale sub array ripetuto di dimensione 1 o maggiore di 1. Ad esempio, considerare un array
1 2 4 1 2 4 1 5 6 3 5, qui
1 viene ripetuto 2 volte
2 si ripete 1 volta
4 si ripete 1 volta
5 viene ripetuto 1 volta
1 2 viene ripetuto 1 volta
2 4 si ripete 1 volta
4 1 viene ripetuta 1 volta
1 2 4 viene ripetuto 1 volta
2 4 1 viene ripetuto 1 volta
1 2 4 1 si ripete 1 volta
Quindi la risposta finale è la somma di questi, ad esempio 11
Qualcuno può suggerire una struttura dati o un algoritmo efficiente per risolvere questo problema. Stavo pensando all'hashing e all'individuazione del valore dell'indice dove si verifica ma non lo ha formalizzato.
Assumere n,m < 10^5

Answer 1

1. Creare un hash con numeri interi come chiavi ed elenchi estendibili (elenchi concatenati, ad esempio) di numeri interi come valori.

2. Leggere l'elenco di input. Tratta ogni elemento di input scansionato come una chiave; aggiungere l'indice del seguente elemento all'elenco di valori associato.

3. Ora, il numero ripetuto di 1 elemento è n - | keys |

4. Quindi, passa le chiavi. Per ogni chiave, considera gli elementi indicizzati dell'elenco originale come una nuova lista di input. Crea un nuovo hash e continua come al punto 1.Si noti che quando memorizziamo gli indici continuiamo a utilizzare quelli dell'elenco originale.

Esempio: 1 2 4 1 2 4 1 5 6 3 5 (supponiamo di avere un indice zero). Qui, n = 11.

• 1 -> [1, 4, 7]
• 2 -> [2, 5]
• 3 -> [10]
• 4 -> [3, 6]
• 5 -> [8, nil]
• 6 -> [9]

Il numero di ripetute 1-PFU è di 11 - 6 = 5.

Ora, passiamo attraverso le chiavi. Iniziamo con 1. La lista degli indici è [1, 4, 7] che corrisponde agli elementi [2, 2, 5].

• 2 -> [2, 5]
• 5 -> [8]

Questa raccoglie 3 - 2 = 1 duplicato elenco 2 elementi.

ecc ...

Durata: lineare in ingresso + uscita

Answer 2

Ho usato un approccio basato sugli alberi di suffisso, da Skienna's book on the design of algorithms. Gli alberi suffissi sono un tipo speciale di trie tree, in cui si inserisce ogni suffisso della stringa data nell'albero trie. Gli alberi Trie sono un modo per memorizzare più parole in un singolo albero: la radice è la stringa nulla e ogni lato aggiunge un carattere. Di seguito ho utilizzato un'implementazione molto semplice come prova del concetto.

#include <iostream> 
#include <string> 
using std::string; 
using std::cout; 

class Node 
{ 
    Node* m_descendants[10]; 
    int m_count; 
public: 
    Node() 
    { 
     for(int i=0; i<10; ++i) { m_descendants[i] = nullptr; } 
     m_count = 0; 
    } 
    void Add(const char* str) { 
     // Increment number of times we've reached this node 
     m_count++; 

     const int firstDigit = str[0] - '0'; 
     if (!(0 <= firstDigit && firstDigit <= 9)) return; // recursion base case 

     // Access descendant node correponding to current digit 
     Node*& descendant = m_descendants[firstDigit]; 
     if (descendant == 0) { // create descendant if necessary 
      descendant = new Node; 
     } 

     // Recurse on rest of string 
     descendant->Add(str +1); 
    } 
    void Print(const string& str, int countAdj=0) const // debug function 
    { 
     for(int nextDigit=0; nextDigit<10; ++nextDigit) { 
      const Node* node = m_descendants[nextDigit]; 
      if (node) { 
       const int adjustedCount = node->Count() - countAdj; 
       if (adjustedCount > 0) { 
        char c = '0' + nextDigit; 
        string strWithC = str; 
        strWithC += c; 
        cout << strWithC << ": " << adjustedCount << "\n"; 
        node->Print(strWithC, countAdj); 
       } 
      } 
     } 
    } 
    int SumRepeated() const 
    { 
     int sumRepeated = 0; 
     for(int nextDigit=0; nextDigit<10; ++nextDigit) { 
      const Node* node = m_descendants[nextDigit]; 
      if (node) { 
       const int repeatCount = node->Count() -1; 
       if (repeatCount > 0) { 
        sumRepeated += repeatCount; 
        sumRepeated += node->SumRepeated(); 
       } 
      } 
     } 
     return sumRepeated; 
    } 
    int Count() const { return m_count; } 
}; 

int main(int argc, const char* argv[]) 
{ 
    // Construct 
    Node* const root = new Node; 
    for(const char* str = "12412415635"; *str; ++str) { 
     root->Add(str); 
    } 

    // Print 
    root->Print(string(), 1); 

    cout << "Sum repeated is " << root->SumRepeated() << "\n"; 

    return 0; // (nodes are leaked) 
} 

uscita

1: 2 
12: 1 
124: 1 
1241: 1 
2: 1 
24: 1 
241: 1 
4: 1 
41: 1 
5: 1 
Sum repeated is 11 

Nota v'è un ulteriore sottostringa ripetuto qui, vale a dire 1241.

Come ho già detto, questa è la prova di concetto, così, per esempio, che ci si vuole utilizzare un dizionario invece di una matrice per memorizzare i discendenti, con più grande m. Inoltre, questa implementazione non è ottimale nemmeno in termini di algoritmo complessivo: è O (n^2) nel tempo e nello spazio. Puoi ottimizzare cracciando i percorsi senza branching per ottenere lo spazio O (n) e utilizzare algoritmi di costruzione intelligenti per ottenere il tempo O (n). Inoltre, come indicato in una delle altre risposte, non è necessario elaborare stringhe secondarie di lunghezza pari a metà della lunghezza dell'originale.

Answer 3

ecco qualcosa in JavaScript: (uscita è più o meno immediato e JavaScript è una delle più lente, credo):

<script> 

function f (s, m) { 
    var i = 0, n = s.length, c = 0, H = {}, Hi = {} 
    while (i < n-1) { 
    for (var j=i+1; j<=Math.min (i + 1 + m,n - 1); j++) { 
     if (s[i] == s[j]) { 
     var i_= i, j_= j, tmp = '' 
     while (s[i_] == s[j_] && i_ < j) { 
      tmp += String (s[i_]) 
      i_++ 
      j_++ 
     } 
     var k = tmp.length - 1 
     while (k >= 0) { 
      if (!H[tmp]) { 
      H[tmp] = 1 
      Hi[tmp] = i 
      c++ 
      } 
      else if (i == Hi[tmp]) { 
      H[tmp]++ 
      c++ 
      } 
      tmp = tmp.substr(0,k--) 
     } 
     } 
    } 
    i++ 
    } 
    var t1 = '' 
    for (var i in H) t1 += i + ", " 
    return [t1,c] 
} 

var a1 = [1,2,4,1,2,4,1,5,6,3,5], 
    a2 = [] 

for (var i=0;i<100000;i++) a2.push(Math.floor(Math.random()*10)) 

console.log(a1 +"\n"+ f(a1,10)) 
console.log(f(a2,10)) 

</script> 

uscita:

1,2,4,1,2,4,1,5,6,3,5 
1, 2, 4, 5, 12, 24, 41, 124, 241, ,10 

["0...6358, 3582, 038, 4304, 2068, 095, 
9252, 37866, 3786, 7866, 7893, 8701, 0669, ", 771]