Scrivere un algoritmo efficiente per trovare il prefisso comune (LCP) più lungo tra un dato insieme di stringhe.
Per esempio,
Input: technique, technician, technology, technical
Output: The longest common prefix is techn
Input: techie delight, tech, techie, technology, technical
Output: The longest common prefix is tech
Output: The longest common prefix is techn
Input: techie delight, tech, techie, technology, technical
Output: The longest common prefix is tech
Una soluzione semplice consiste nel considerare ogni stringa e calcolare il suo prefisso comune più lungo con il prefisso comune più lungo delle stringhe elaborate finora. La complessità temporale di questa soluzione è O(N.M), dove N è il numero totale di parole e M è la lunghezza massima di una parola.
Questo è dimostrato di seguito in C++, Java e Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#include <iostream> #include <vector> #include <string> using namespace std; // Funzione per trovare il prefisso comune più lungo tra due stringhe string LCP(string X, string Y) { int i = 0, j = 0; while (i < X.length() && j < Y.length()) { if (X[i] != Y[j]) { break; } i++, j++; } return X.substr(0, i); } // Funzione per trovare il prefisso comune (LCP) più lungo tra un determinato insieme di stringhe string findLCP(vector<string> const &words) { string prefix = words[0]; for (string s: words) { prefix = LCP(prefix, s); } return prefix; } int main() { vector<string> words { "techie delight", "tech", "techie", "technology", "technical" }; cout << "The longest common prefix is " << findLCP(words); return 0; } |
Risultato:
The longest common prefix is tech
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
import java.util.Arrays; import java.util.List; class Main { // Funzione per trovare il prefisso comune più lungo tra due stringhe public static String LCP(String X, String Y) { int i = 0, j = 0; while (i < X.length() && j < Y.length()) { if (X.charAt(i) != Y.charAt(j)) { break; } i++; j++; } return X.substring(0, i); } // Funzione per trovare il prefisso comune (LCP) più lungo tra un determinato insieme di stringhe public static String findLCP(List<String> words) { String prefix = words.get(0); for (String s: words) { prefix = LCP(prefix, s); } return prefix; } public static void main(String[] args) { List<String> words = Arrays.asList("techie delight", "tech", "techie", "technology", "technical"); System.out.println("The longest common prefix is " + findLCP(words)); } } |
Risultato:
The longest common prefix is tech
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
# Funzione per trovare il prefisso comune più lungo tra due stringhe def LCP(X, Y): i = j = 0 while i < len(X) and j < len(Y): if X[i] != Y[j]: break i = i + 1 j = j + 1 return X[:i] # Funzione per trovare il prefisso comune (LCP) più lungo tra un determinato insieme di stringhe def findLCP(words): prefix = words[0] for s in words: prefix = LCP(prefix, s) return prefix if __name__ == '__main__': words = ['techie delight', 'tech', 'techie', 'technology', 'technical'] print('The longest common prefix is', findLCP(words)) |
Risultato:
The longest common prefix is tech
Possiamo anche usare il Dividi e conquista tecnica per trovare il prefisso comune più lungo (LCP). Come tutti gli algoritmi divide et impera, l'idea è di dividere le stringhe in due insiemi più piccoli e quindi elaborare ricorsivamente tali insiemi. Questo è simile al unisci ordinamento routine, tranne per il fatto che troviamo l'LCP delle due metà invece di unire entrambe le metà.
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#include <iostream> #include <vector> #include <string> using namespace std; // Funzione per trovare il prefisso comune più lungo tra due stringhe string LCP(string X, string Y) { int i = 0, j = 0; while (i < X.length() && j < Y.length()) { if (X[i] != Y[j]) { break; } i++, j++; } return X.substr(0, i); } // Una funzione ricorsivo per trovare il prefisso comune (LCP) più lungo tra a // dato set di stringhe string findLCP(vector<string> const &words, int low, int high) { // caso base: se `low` è maggiore di `high`, restituisce una stringa vuota if (low > high) { return string(""); } // caso base: se `low` è uguale a `high`, restituisce la stringa corrente if (low == high) { return words[low]; } // trova l'indice medio int mid = (low + high) / 2; // suddivide il problema in sottoproblemi e ricorre per ogni sottoproblema string X = findLCP(words, low, mid); string Y = findLCP(words, mid + 1, high); // restituisce il prefisso comune più lungo delle stringhe `X` e `Y` return LCP(X, Y); } int main() { vector<string> words = { "techie delight", "tech", "techie", "technology", "technical" }; cout << "The longest common prefix is " << findLCP(words, 0, words.size() - 1); return 0; } |
Risultato:
The longest common prefix is tech
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
import java.util.Arrays; import java.util.List; class Main { // Funzione per trovare il prefisso comune più lungo tra due stringhe public static String LCP(String X, String Y) { int i = 0, j = 0; while (i < X.length() && j < Y.length()) { if (X.charAt(i) != Y.charAt(j)) { break; } i++; j++; } return X.substring(0, i); } // Una funzione ricorsivo per trovare il prefisso comune (LCP) più lungo tra a // dato set di stringhe public static String findLCP(List<String> words, int low, int high) { // caso base: se `low` è maggiore di `high`, restituisce una stringa vuota if (low > high) { return ""; } // caso base: se `low` è uguale a `high`, restituisce la stringa corrente if (low == high) { return words.get(low); } // trova l'indice medio int mid = (low + high) / 2; // suddivide il problema in sottoproblemi e ricorre per ogni sottoproblema String X = findLCP(words, low, mid); String Y = findLCP(words, mid + 1, high); // restituisce il prefisso comune più lungo delle stringhe `X` e `Y` return LCP(X, Y); } public static void main(String[] args) { List<String> words = Arrays.asList("techie delight", "tech", "techie", "technology", "technical"); System.out.println("The longest common prefix is " + findLCP(words, 0, words.size() - 1)); } } |
Risultato:
The longest common prefix is tech
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
# Funzione per trovare il prefisso comune più lungo tra due stringhe def LCP(X, Y): i = j = 0 while i < len(X) and j < len(Y): if X[i] != Y[j]: break i = i + 1 j = j + 1 return X[:i] # Una funzione ricorsivo per trovare il prefisso comune (LCP) più lungo tra a # dato insieme di stringhe def findLCP(words, low, high): # Caso base #: se `low` è maggiore di `high`, restituisce una stringa vuota if low > high: return '' # Caso base #: se `low` è uguale a `high`, restituisce la stringa corrente if low == high: return words[low] # trova l'indice medio mid = (low + high) // 2 # suddivide il problema in sottoproblemi e ricorre per ogni sottoproblema X = findLCP(words, low, mid) Y = findLCP(words, mid + 1, high) # restituisce il prefisso comune più lungo delle stringhe `X` e `Y` return LCP(X, Y) if __name__ == '__main__': words = ['techie delight', 'tech', 'techie', 'technology', 'technical'] print('The longest common prefix is', findLCP(words, 0, len(words) - 1)) |
Risultato:
The longest common prefix is tech
La complessità temporale della soluzione di cui sopra è O(N.M), dove N è il numero totale di parole e M è la lunghezza massima di una parola. Lo spazio ausiliario utilizzato è O(M.log(N)) per lo call stack.
Vedi anche:
Prefisso comune più lungo in un dato set di stringhe (usando Trie)