Algorithmus - alle Permutationen der Zeichenfolge ein in Zeichenfolge finden b

Question

Sagen wir string a = "abc" String b = "abcdcabaabccbaa"

Suche Lage aller Permutationen von a in b haben. Ich versuche einen effektiven Algorithmus dafür zu finden.

Pseudo-Code:

sort string a // O(a loga) 

for windows of length a in b // O(b)? 
    sort that window of b  // O(~a loga)? 
    compare to a 
    if equal 
     save the index 

würde dies also ein richtiger Algorithmus sein? Laufzeit wäre um O (aloga + ba loga) ~ = O (a loga b)? Wie effizient wäre das? Eventuell auf O (a * b) oder besser reduzieren?

Answer 1

Sortierung ist sehr teuer, und nutzt nicht die Tatsache, dass Sie entlang b mit einem Schiebefenster bewegen.

Ich würde eine Vergleichsmethode verwenden, die ortsunabhängig ist (da jede Permutation gültig ist) - weisen Sie jedem Buchstaben eine Primzahl zu, und jeder String ist die Multiplikation seiner Buchstabenwerte.

so, wie Sie über b gehen, erfordert jeder Schritt nur Division durch den Buchstaben, den Sie von links entfernen, und multipliziert mit dem nächsten Buchstaben.

Sie müssen sich auch selbst davon überzeugen, dass dies in der Tat für jede Zeichenfolge eindeutig übereinstimmt und alle Permutationen abdeckt - dies kommt von der Einzigartigkeit der primären Zerlegung. Beachten Sie auch, dass bei großen Strings die Zahlen groß werden, so dass Sie möglicherweise eine Bibliothek für große Zahlen benötigen.

Answer 2

Schreiben Sie eine Funktion strcount(), um die Anzahl der Vorkommen von Zeichen ch in einer Zeichenfolge oder sub-sring str zu zählen.

Dann nur die Suchzeichenfolge durchlaufen.

for(i=0;i<haystacklenN-NeedleN+1;i++) 
    { 
    for(j=0;j<needleN;j++) 
     if(strcount(haystack + i, Nneedle, needle[j]) != strcount(needles, needlesN, needle[j]) 
     break 
    } 
    if(j == needleN) 
     /* found a permuatation */ 

Answer 3

Sie müssen nicht hash, Sie können nur Frequenzen in Ihrem gleitenden Fenster zählen und prüfen, ob es übereinstimmt. Unter der Annahme, dass die Größe Ihres Alphabets s ist, erhalten Sie einen sehr einfachen O(s(n + m)) Algorithmus.

// a = [1 .. m] and b = [1 .. n] are the input 
cnta = [1 .. s] array initialized to 0 
cntb = [1 .. s] array initialized to 0 
// nb_matches = the number of i s.t. cnta[i] = cntb[i] 
// thus the current subword = a iff. nb_matches = s 
nb_matches = s 

for i = 1 to m: 
    if cntb[a[i]] = 0: nb_matches -= 1 
    cntb[a[i]] += 1 

ans = 0 
for i = 1 to n: 
    if cntb[b[i]] = cnta[b[i]]: nb_matches -= 1 
    cntb[b[i]] += 1 
    if nb_matches = s: ans += 1 
    if cntb[b[i]] = cnta[b[i]]: nb_matches += 1 
    if i - m + 1 >= 1: 
     if cntb[b[i - m + 1]] = cnta[b[i - m + 1]]: nb_matches -= 1 
     cntb[b[i - m + 1]] += 1 
     if cntb[b[i - m + 1]] = cnta[b[i - m + 1]]: nb_matches += 1 
     cntb[b[i - m + 1]] -= 1 
return ans 

Answer 4

Unten ist meine Lösung. Die Raumkomplexität ist nur O(a + b), und die Laufzeit (wenn ich kann richtig berechnen ..) ist O(b*a), wie für jedes Zeichen in b, können wir eine Rekursion a Ebenen tief.

md5's Antwort ist eine gute und wird schneller sein !!

public class FindPermutations { 
public static void main(String[] args) { 

    System.out.println(numPerms(new String("xacxzaa"), 
      new String("fxaazxacaaxzoecazxaxaz"))); 
    System.out.println(numPerms(new String("ABCD"), 
      new String("BACDGABCDA"))); 
    System.out.println(numPerms(new String("AABA"), 
      new String("AAABABAA"))); 

    // prints 4, then 3, then 3 
} 

public static int numPerms(final String a, final String b) { 
    int sum = 0; 
    for (int i = 0; i < b.length(); i++) { 
     if (permPresent(a, b.substring(i))) { 
      sum++; 
     } 
    } 
    return sum; 
} 

// is a permutation of a present at the start of b? 
public static boolean permPresent(final String a, final String b) { 
    if (a.isEmpty()) { 
     return true; 
    } 

    if (b.isEmpty()) { 
     return false; 
    } 

    final char first = b.charAt(0); 
    if (a.contains(b.substring(0, 1))) { 
     // super ugly, but removes first from a 
     return permPresent(a.substring(0, a.indexOf(first)) + a.substring(a.indexOf(first)+1, a.length()), 
       b.substring(1)); 
    } 
    return false; 
} 
} 

Aus Gründen der Auffindbarkeit, komme ich auf dieser Seite afer nach anderen Lösungen suchen Mine, mit dem Problem aus der Beobachtung dieser Clip Ursprung zu vergleichen: https://www.hackerrank.com/domains/tutorials/cracking-the-coding-interview. Die ursprüngliche Problembeschreibung war etwas wie "finde alle Permutationen von s in b".