Generiere alle eindeutigen Teilstrings für eine gegebene Zeichenkette

Gibt es eine Zeichenfolge s , was ist die schnellste Methode, um eine Menge aller eindeutigen Teilzeichenfolgen zu generieren?

Beispiel: für str = "aba" würden wir substrs={"a", "b", "ab", "ba", "aba"} .

Der naive Algorithmus würde die gesamte Zeichenfolge, die Teilstrings erzeugt, in der Länge 1..n in jeder Iteration 1..n , was eine O(n^2) obere Grenze ergibt.

Ist eine bessere Bindung möglich?

(das ist technisch Hausaufgaben, also sind auch nur pointers willkommen)

   

Wie andere Poster gesagt haben, gibt es potenziell O (n ^ 2) Teilstrings für eine gegebene Zeichenkette, so dass sie nicht schneller ausgedruckt werden können. Es gibt jedoch eine effiziente Repräsentation der Menge, die in linearer Zeit konstruiert werden kann: der Suffixbaum .

Es gibt keine Möglichkeit, dies schneller als O (n 2 ) zu tun, weil es insgesamt O (n 2 ) Teilstrings in einem String gibt. Wenn Sie also alle generieren müssen, ist ihre Zahl n(n + 1) / 2 im schlechtesten Fall, daher die obere untere Grenze von O (n 2 ) Ω (n 2 ).

Die erste ist die Brute Force mit der Komplexität O (N ^ 3), die auf O (N ^ 2 log (N) reduziert werden kann) Zweite mit HashSet mit der Komplexität O (N ^ 2) Third One mit LCP durch anfängliches Auffinden das ganze Suffix einer gegebenen Zeichenfolge, die den schlechtesten Fall O (N ^ 2) und besten Fall O (N Log (N)) aufweist.

Erste Lösung: –

 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 

Zweite Lösung: -

 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"); } } 

Dritte Lösung: -

 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); } } 

Vierte Lösung: -

  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"); 

Für großes oh … Das Beste, was du tun könntest, wäre O (n ^ 2)

Keine Notwendigkeit, das Rad neu zu erfinden, es basiert nicht auf Strings, sondern auf Sets, also müssen Sie die Konzepte übernehmen und auf Ihre eigene Situation anwenden.

Algorithmen

Wirklich gutes White Paper von MS

Eingehend PowerPoint

Blog auf String-Dauerwellen

Nun, da es potentiell n*(n+1)/2 verschiedene Teilstrings (+1 für die leere Teilkette) gibt, bezweifle ich, dass du besser sein kannst als O(n*2) (schlimmster Fall). Am einfachsten ist es, sie zu generieren und eine nette O(1) -Nachschlagetabelle (z. B. eine Hashmap) zu verwenden, um Duplikate auszuschließen, wenn Sie sie gefunden haben.

 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); } } } } 

Dies kann nur in der Zeit o (n ^ 2) erfolgen, da die Gesamtzahl eindeutiger Teilstrings einer Kette n (n + 1) / 2 wäre.

Beispiel:

Zeichenfolge s = “abcd”

Pass 0: (alle Strings haben die Länge 1)

a, b, c, d = 4 Saiten

Pass 1: (alle Saiten haben die Länge 2)

ab, bc, cd = 3 Saiten

Pass 2: (alle Saiten haben die Länge 3)

abc, bcd = 2 Zeichenfolgen

Pass 3: (alle Saiten haben die Länge 4)

abcd = 1 Zeichenfolgen

Unter Verwendung dieser Analogie können wir eine Lösung mit einer Zeitkomplexität von o (n ^ 2) und einer konstanten Raumkomplexität schreiben.

Der Quellcode ist wie folgt:

 #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; } 

Hier ist mein Code in Python. Es erzeugt alle möglichen Teilstrings einer gegebenen Zeichenkette.

 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) 

Wenn Sie str_ = "abcdef" an die function übergeben, werden folgende Ergebnisse generiert:

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

Der naive Algorithmus benötigt O (n ^ 3) Zeit anstatt O (n ^ 2) Zeit. Es gibt O (n ^ 2) Anzahl von Teilstrings. Und wenn Sie beispielsweise O (n ^ 2) Anzahl von Teilstrings setzen, dann vergleicht set O (lgn) Vergleiche für jede Zeichenkette, um zu prüfen, ob sie bereits in der Menge existiert oder nicht. Außerdem benötigt es O (n) Zeit für den String Vergleich. Daher dauert es 0 (n ^ 3 lgn) Zeit, wenn Sie set verwenden. und Sie können es reduzieren O (n ^ 3) Zeit, wenn Sie Hashtable statt set verwenden.

Der Punkt ist, dass Zeichenkettenvergleiche keine Zahlenvergleiche sind.

Einer der besten Algorithmen lässt also sagen, wenn Sie den Suffix-Array und den LCP-Algorithmus (Long Common Prefix) verwenden, verringert sich die Zeit von O (n ^ 2) für dieses Problem. Erstellen eines Suffix-Arrays mit dem O (n) -Zeitalgorithmus. Zeit für LCP = O (n) Zeit. Da für jedes Paar von Strings im Suffix-Array LCP durchgeführt wird, ist die Gesamtzeit O (n ^ 2) Zeit, um die Länge von verschiedenen Subtringen zu finden.

Außerdem, wenn Sie alle verschiedenen Teilstrings drucken möchten, dauert es O (n ^ 2) Zeit.

Dies druckt eindeutige Teilstrings. 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'] 

Versuchen Sie diesen Code mit einem Suffix-Array und dem längsten gemeinsamen Präfix. Es kann Ihnen auch die Gesamtzahl der eindeutigen Teilstrings geben. Der Code könnte einen Stapelüberlauf in Visual Studio verursachen, läuft aber in Eclipse C ++ einwandfrei. Das ist, weil es Vektoren für functionen zurückgibt. Habe es nicht mit extrem langen Saiten getestet. Tun Sie es und melden Sie sich zurück.

  // 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; } 

Und hier ist ein einfacherer Algorithmus:

 #include  #include  #include  #include  #include  #include  

Beide Algorithmen listeten allerdings für extrem lange Saiten einfach zu langsam auf. Ich testete die Algorithmen gegen eine Saite mit einer Länge von über 47.000, und die Algorithmen dauerten mehr als 20 Minuten, wobei die erste 1200 Sekunden dauerte und die zweite 1360 Sekunden, und das zählt nur die eindeutigen Teilstrings ohne Ausgabe an das Terminal. Also für wahrscheinlich Kettenlängen bis zu 1000 können Sie eine funktionierende Lösung bekommen. Beide Lösungen berechneten jedoch die gleiche Gesamtzahl an eindeutigen Teilstrings. Ich habe beide Algorithmen gegen Stringlängen von 2000 und 10.000 getestet. Die Zeiten waren für den ersten Algorithmus: 0,33 s und 12 s; für den zweiten Algorithmus war es 0,535 s und 20 s. So sieht es im Allgemeinen aus, dass der erste Algorithmus schneller ist.

Ihre Programme geben keine eindeutigen sbstrins.

Bitte testen Sie mit Eingabeabab und Ausgabe sollte aba,ba,bab,abab .