Generar todas las subcadenas únicas para una cadena dada

Dada una cadena s , ¿cuál es el método más rápido para generar un conjunto de todas sus subcadenas únicas?

Ejemplo: para str = "aba" obtendríamos substrs={"a", "b", "ab", "ba", "aba"} .

El algoritmo ingenuo sería atravesar las subcadenas de generación de cadenas completas en longitud 1..n en cada iteración, produciendo un límite superior O(n^2) .

¿Es posible un mejor límite?

(Esto es técnicamente tarea, por lo que también son bienvenidos solo los apuntadores)

Como han dicho otros carteles, hay potencialmente subcadenas O (n ^ 2) para una cadena dada, por lo que imprimirlas no se puede hacer más rápido que eso. Sin embargo, existe una representación eficiente del conjunto que se puede construir en tiempo lineal: el árbol de sufijos .

No hay forma de hacerlo más rápido que O (n 2 ) porque hay un total de subcadenas O (n 2 ) en una cadena, por lo que si tiene que generarlas todas , su número será n(n + 1) / 2 en el peor de los casos, de ahí el límite inferior superior de O (n 2 ) Ω (n 2 ).

La primera es la fuerza bruta que tiene una complejidad O (N ^ 3) que puede reducirse a O (N ^ 2 log (N)) Segunda usando HashSet que tiene Complejidad O (N ^ 2) Tercera usando LCP encontrando inicialmente todo el sufijo de una cadena dada que tiene el peor caso O (N ^ 2) y el mejor caso O (N Log (N)).

Primera solución: –

 import java.util.Scanner; public class DistinctSubString { public static void main(String[] args) { Scanner in = new Scanner(System.in); System.out.print("Enter The string"); String s = in.nextLine(); long startTime = System.currentTimeMillis(); int L = s.length(); int N = L * (L + 1) / 2; String[] Comb = new String[N]; for (int i = 0, p = 0; i < L; ++i) { for (int j = 0; j < (L - i); ++j) { Comb[p++] = s.substring(j, i + j + 1); } } /* * for(int j=0;j 

Segunda solución: -

 import java.util.*; public class DistictSubstrings_usingHashTable { public static void main(String args[]) { // create a hash set Scanner in = new Scanner(System.in); System.out.print("Enter The string"); String s = in.nextLine(); int L = s.length(); long startTime = System.currentTimeMillis(); Set hs = new HashSet(); // add elements to the hash set for (int i = 0; i < L; ++i) { for (int j = 0; j < (L - i); ++j) { hs.add(s.substring(j, i + j + 1)); } } System.out.println(hs.size()); long endTime = System.currentTimeMillis(); System.out.println("It took " + (endTime - startTime) + " milliseconds"); } } 

Tercera solución:

 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class LCPsolnFroDistinctSubString { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); System.out.println("Enter Desired String "); String string = br.readLine(); int length = string.length(); String[] arrayString = new String[length]; for (int i = 0; i < length; ++i) { arrayString[i] = string.substring(length - 1 - i, length); } Arrays.sort(arrayString); for (int i = 0; i < length; ++i) System.out.println(arrayString[i]); long num_substring = arrayString[0].length(); for (int i = 0; i < length - 1; ++i) { int j = 0; for (; j < arrayString[i].length(); ++j) { if (!((arrayString[i].substring(0, j + 1)).equals((arrayString)[i + 1] .substring(0, j + 1)))) { break; } } num_substring += arrayString[i + 1].length() - j; } System.out.println("unique substrings = " + num_substring); } } 

Cuarta solución:

  public static void printAllCombinations(String soFar, String rest) { if(rest.isEmpty()) { System.out.println(soFar); } else { printAllCombinations(soFar + rest.substring(0,1), rest.substring(1)); printAllCombinations(soFar , rest.substring(1)); } } Test case:- printAllCombinations("", "abcd"); 

Para grande oh … Lo mejor que podrías hacer sería O (n ^ 2)

No es necesario reinventar la rueda, no se basa en cuerdas, sino en conjuntos, por lo que deberá tomar los conceptos y aplicarlos a su propia situación.

Algoritmos

Muy buen libro blanco de MS

En profundidad PowerPoint

Blog en perms de cadena

bueno, dado que potencialmente hay n*(n+1)/2 subcadenas diferentes (+1 para la subcadena vacía), dudo que puedas ser mejor que O(n*2) (el peor de los casos). lo más fácil es generarlos y usar una buena tabla de búsqueda de O(1) (como un hashmap) para excluir duplicados cuando los encuentres.

 class program { List lst = new List(); String str = "abc"; public void func() { subset(0, ""); lst.Sort(); lst = lst.Distinct().ToList(); foreach (String item in lst) { Console.WriteLine(item); } } void subset(int n, String s) { for (int i = n; i < str.Length; i++) { lst.Add(s + str[i].ToString()); subset(i + 1, s + str[i].ToString()); } } } 
 class SubstringsOfAString { public static void main(String args[]) { String string = "Hello", sub = null; System.out.println("Substrings of \"" + string + "\" are :-"); for (int i = 0; i < string.length(); i++) { for (int j = 1; j <= string.length() - i; j++) { sub = string.substring(i, j + i); System.out.println(sub); } } } } 

Solo se puede hacer en o (n ^ 2) tiempo ya que el número total de subcadenas únicas de una cadena sería n (n + 1) / 2.

Ejemplo:

cadena s = “abcd”

pasar 0: (todas las cadenas son de longitud 1)

a, b, c, d = 4 cuerdas

pase 1: (todas las cuerdas son de longitud 2)

ab, bc, cd = 3 cuerdas

pase 2: (todas las cuerdas son de longitud 3)

abc, bcd = 2 cuerdas

pase 3: (todas las cuerdas son de longitud 4)

abcd = 1 cuerdas

Usando esta analogía, podemos escribir solución con o (n ^ 2) complejidad de tiempo y complejidad de espacio constante.

El código fuente es el siguiente:

 #include void print(char arr[], int start, int end) { int i; for(i=start;i<=end;i++) { printf("%c",arr[i]); } printf("\n"); } void substrings(char arr[], int n) { int pass,j,start,end; int no_of_strings = n-1; for(pass=0;pass=0;j--) { print(arr,start, end); start++; end = start+pass; } no_of_strings--; } } int main() { char str[] = "abcd"; substrings(str,4); return 0; } 

Aquí está mi código en Python. Genera todas las subcadenas posibles de cualquier cadena dada.

 def find_substring(str_in): substrs = [] if len(str_in) <= 1: return [str_in] s1 = find_substring(str_in[:1]) s2 = find_substring(str_in[1:]) substrs.append(s1) substrs.append(s2) for s11 in s1: substrs.append(s11) for s21 in s2: substrs.append("%s%s" %(s11, s21)) for s21 in s2: substrs.append(s21) return set(substrs) 

Si pasa str_ = "abcdef" a la función, genera los siguientes resultados:

a, ab, abc, abcd, abcde, abcdef, abcdf, abce, abcef, abcf, abd, abde, abdef, abdf, abe, abef, abf, ac, acd, acde, acdef, acdf, as, acef, acf, ad, ade, adef, adf, ae, aef, af, b, bc, bcd, bcde, bcdef, bcdf, bce, bcef, bcf, bd, bde, bdef, bdf, ser, bef, bf, c, cd, cde, cdef, cdf, ce, cef, cf, d, de, def, df, e, ef, f

El algoritmo ingenuo toma O (n ^ 3) tiempo en lugar de O (n ^ 2) tiempo. Hay O (n ^ 2) cantidad de subcadenas. Y si pone O (n ^ 2) número de subcadenas, por ejemplo, establecer, entonces establecer compara comparaciones O (lgn) para cada cadena para verificar si existe o no en el conjunto. Además, toma O (n) tiempo para la comparación de cadenas. Por lo tanto, toma O (n ^ 3 lgn) tiempo si usa set. y puede reducirlo O (n ^ 3) tiempo si usa hashtable en lugar de set.

El punto es que las comparaciones de cuerdas no son comparaciones numéricas.

Entonces, uno de los mejores algoritmos, digamos que si usa la matriz de sufijos y el algoritmo de prefijo común más largo (LCP), reduce el tiempo O (n ^ 2) para este problema. Construyendo una matriz de sufijo usando el algoritmo O (n) time. Tiempo para LCP = O (n) tiempo. Dado que para cada par de cadenas en la matriz de sufijos, haga LCP, entonces el tiempo total es O (n ^ 2) tiempo para encontrar la longitud de distintas subcadenas.

Además, si desea imprimir todas las subcadenas distintas, se necesita O (n ^ 2) tiempo.

Esto imprime subcadenas únicas. https://ideone.com/QVWOh0

 def uniq_substring(test): lista=[] [lista.append(test[i:i+k+1]) for i in range(len(test)) for k in range(len(test)-i) if test[i:i+k+1] not in lista and test[i:i+k+1][::-1] not in lista] print lista uniq_substring('rohit') uniq_substring('abab') ['r', 'ro', 'roh', 'rohi', 'rohit', 'o', 'oh', 'ohi', 'ohit', 'h', 'hi', 'hit', 'i', 'it', 't'] ['a', 'ab', 'aba', 'abab', 'b', 'bab'] 

Pruebe este código usando una matriz de sufijos y el prefijo común más largo. También le puede dar el número total de subcadenas únicas. El código puede dar un desbordamiento de stack en Visual Studio pero funciona bien en Eclipse C ++. Eso es porque devuelve vectores para funciones. No lo he probado contra cadenas extremadamente largas. Lo hará e informará de nuevo.

  // C++ program for building LCP array for given text #include  #include  #include  using namespace std; #define MAX 100000 int cum[MAX]; // Structure to store information of a suffix struct suffix { int index; // To store original index int rank[2]; // To store ranks and next rank pair }; // A comparison function used by sort() to compare two suffixes // Compares two pairs, returns 1 if first pair is smaller int cmp(struct suffix a, struct suffix b) { return (a.rank[0] == b.rank[0])? (a.rank[1] < b.rank[1] ?1: 0): (a.rank[0] < b.rank[0] ?1: 0); } // This is the main function that takes a string 'txt' of size n as an // argument, builds and return the suffix array for the given string vector buildSuffixArray(string txt, int n) { // A structure to store suffixes and their indexes struct suffix suffixes[n]; // Store suffixes and their indexes in an array of structures. // The structure is needed to sort the suffixes alphabatically // and maintain their old indexes while sorting for (int i = 0; i < n; i++) { suffixes[i].index = i; suffixes[i].rank[0] = txt[i] - 'a'; suffixes[i].rank[1] = ((i+1) < n)? (txt[i + 1] - 'a'): -1; } // Sort the suffixes using the comparison function // defined above. sort(suffixes, suffixes+n, cmp); // At his point, all suffixes are sorted according to first // 2 characters. Let us sort suffixes according to first 4 // characters, then first 8 and so on int ind[n]; // This array is needed to get the index in suffixes[] // from original index. This mapping is needed to get // next suffix. for (int k = 4; k < 2*n; k = k*2) { // Assigning rank and index values to first suffix int rank = 0; int prev_rank = suffixes[0].rank[0]; suffixes[0].rank[0] = rank; ind[suffixes[0].index] = 0; // Assigning rank to suffixes for (int i = 1; i < n; i++) { // If first rank and next ranks are same as that of previous // suffix in array, assign the same new rank to this suffix if (suffixes[i].rank[0] == prev_rank && suffixes[i].rank[1] == suffixes[i-1].rank[1]) { prev_rank = suffixes[i].rank[0]; suffixes[i].rank[0] = rank; } else // Otherwise increment rank and assign { prev_rank = suffixes[i].rank[0]; suffixes[i].rank[0] = ++rank; } ind[suffixes[i].index] = i; } // Assign next rank to every suffix for (int i = 0; i < n; i++) { int nextindex = suffixes[i].index + k/2; suffixes[i].rank[1] = (nextindex < n)? suffixes[ind[nextindex]].rank[0]: -1; } // Sort the suffixes according to first k characters sort(suffixes, suffixes+n, cmp); } // Store indexes of all sorted suffixes in the suffix array vectorsuffixArr; for (int i = 0; i < n; i++) suffixArr.push_back(suffixes[i].index); // Return the suffix array return suffixArr; } /* To construct and return LCP */ vector kasai(string txt, vector suffixArr) { int n = suffixArr.size(); // To store LCP array vector lcp(n, 0); // An auxiliary array to store inverse of suffix array // elements. For example if suffixArr[0] is 5, the // invSuff[5] would store 0. This is used to get next // suffix string from suffix array. vector invSuff(n, 0); // Fill values in invSuff[] for (int i=0; i < n; i++) invSuff[suffixArr[i]] = i; // Initialize length of previous LCP int k = 0; // Process all suffixes one by one starting from // first suffix in txt[] for (int i=0; i0) k--; } // return the constructed lcp array return lcp; } // Utility function to print an array void printArr(vectorarr, int n) { for (int i = 0; i < n; i++) cout << arr[i] << " "; cout << endl; } // Driver program int main() { int t; cin >> t; //t = 1; while (t > 0) { //string str = "banana"; string str; cin >> str; // >> k; vectorsuffixArr = buildSuffixArray(str, str.length()); int n = suffixArr.size(); cout << "Suffix Array : \n"; printArr(suffixArr, n); vectorlcp = kasai(str, suffixArr); cout << "\nLCP Array : \n"; printArr(lcp, n); // cum will hold number of substrings if that'a what you want (total = cum[n-1] cum[0] = n - suffixArr[0]; // vector > substrs[n]; int count = 1; for (int i = 1; i <= n-suffixArr[0]; i++) { //substrs[0].push_back({suffixArr[0],i}); string sub_str = str.substr(suffixArr[0],i); cout << count << " " << sub_str << endl; count++; } for(int i = 1;i < n;i++) { cum[i] = cum[i-1] + (n - suffixArr[i] - lcp[i - 1]); int end = n - suffixArr[i]; int begin = lcp[i-1] + 1; int begin_suffix = suffixArr[i]; for (int j = begin, k = 1; j <= end; j++, k++) { //substrs[i].push_back({begin_suffix, lcp[i-1] + k}); // cout << "i push " << i << " " << begin_suffix << " " << k << endl; string sub_str = str.substr(begin_suffix, lcp[i-1] +k); cout << count << " " << sub_str << endl; count++; } } /*int count = 1; cout << endl; for(int i = 0; i < n; i++){ for (auto it = substrs[i].begin(); it != substrs[i].end(); ++it ) { string sub_str = str.substr(it->first, it->second); cout << count << " " << sub_str << endl; count++; } }*/ t--; } return 0; } 

Y aquí hay un algoritmo más simple:

 #include  #include  #include  #include  #include  #include  using namespace std; char txt[100000], *p[100000]; int m, n; int cmp(const void *p, const void *q) { int rc = memcmp(*(char **)p, *(char **)q, m); return rc; } int main() { std::cin >> txt; int start_s = clock(); n = strlen(txt); int k; int i; int count = 1; for (m = 1; m <= n; m++) { for (k = 0; k+m <= n; k++) p[k] = txt+k; qsort(p, k, sizeof(p[0]), &cmp); for (i = 0; i < k; i++) { if (i != 0 && cmp(&p[i-1], &p[i]) == 0){ continue; } char cur_txt[100000]; memcpy(cur_txt, p[i],m); cur_txt[m] = '\0'; std::cout << count << " " << cur_txt << std::endl; count++; } } cout << --count << endl; int stop_s = clock(); float run_time = (stop_s - start_s) / double(CLOCKS_PER_SEC); cout << endl << "distinct substrings \t\tExecution time = " << run_time << " seconds" << endl; return 0; } 

Sin embargo, ambos algoritmos enumeraron simplemente demasiado lento para cadenas extremadamente largas. Probé los algoritmos contra una cadena de longitud superior a 47,000 y los algoritmos tardaron más de 20 minutos en completarse, el primero requirió 1200 segundos, y el segundo tomó 1360 segundos, y eso es solo contar las subcadenas únicas sin enviarlas al terminal. Entonces, para cadenas probablemente de hasta 1000, es posible que obtenga una solución funcional. Ambas soluciones sí calcularon el mismo número total de subcadenas únicas. Probé ambos algoritmos contra longitudes de cadena de 2000 y 10,000. Los tiempos fueron para el primer algoritmo: 0.33 sy 12 s; para el segundo algoritmo fue 0.535 sy 20 s. Entonces, parece que, en general, el primer algoritmo es más rápido.

Sus progtwigs no están dando sbstrins únicos.

Pruebe con abab entrada y la salida debe ser aba,ba,bab,abab .