You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{"payload":{"allShortcutsEnabled":false,"path":"Knuth-Morris-Pratt","repo":{"id":466864423,"defaultBranch":"master","name":"swift-algorithm-club","ownerLogin":"zezzi","currentUserCanPush":false,"isFork":true,"isEmpty":false,"createdAt":"2022-03-06T21:45:56.000Z","ownerAvatar":"https://avatars.githubusercontent.com/u/591679?v=4","public":true,"private":false,"isOrgOwned":false},"currentUser":null,"refInfo":{"name":"Permutations","listCacheKey":"v0:1646603162.973994","canEdit":false,"refType":"branch","currentOid":"3f409c5bcc966326b951a13e3a7ba1f81ab72871"},"tree":{"items":[{"name":"KnuthMorrisPratt.playground","path":"Knuth-Morris-Pratt/KnuthMorrisPratt.playground","contentType":"directory"},{"name":"KnuthMorrisPratt.swift","path":"Knuth-Morris-Pratt/KnuthMorrisPratt.swift","contentType":"file"},{"name":"README.markdown","path":"Knuth-Morris-Pratt/README.markdown","contentType":"file"}],"templateDirectorySuggestionUrl":null,"readme":{"displayName":"README.markdown","richText":"\u003carticle class=\"markdown-body entry-content container-lg\" itemprop=\"text\"\u003e\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch1 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eKnuth-Morris-Pratt String Search\u003c/h1\u003e\u003ca id=\"user-content-knuth-morris-pratt-string-search\" class=\"anchor\" aria-label=\"Permalink: Knuth-Morris-Pratt String Search\" href=\"#knuth-morris-pratt-string-search\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eGoal: Write a linear-time string matching algorithm in Swift that returns the indexes of all the occurrencies of a given pattern.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eIn other words, we want to implement an \u003ccode\u003eindexesOf(pattern: String)\u003c/code\u003e extension on \u003ccode\u003eString\u003c/code\u003e that returns an array \u003ccode\u003e[Int]\u003c/code\u003e of integers, representing all occurrences' indexes of the search pattern, or \u003ccode\u003enil\u003c/code\u003e if the pattern could not be found inside the string.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eFor example:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"let dna = \u0026quot;ACCCGGTTTTAAAGAACCACCATAAGATATAGACAGATATAGGACAGATATAGAGACAAAACCCCATACCCCAATATTTTTTTGGGGAGAAAAACACCACAGATAGATACACAGACTACACGAGATACGACATACAGCAGCATAACGACAACAGCAGATAGACGATCATAACAGCAATCAGACCGAGCGCAGCAGCTTTTAAGCACCAGCCCCACAAAAAACGACAATFATCATCATATACAGACGACGACACGACATATCACACGACAGCATA\u0026quot;\ndna.indexesOf(ptnr: \u0026quot;CATA\u0026quot;) // Output: [20, 64, 130, 140, 166, 234, 255, 270]\n\nlet concert = \u0026quot;🎼🎹🎹🎸🎸🎻🎻🎷🎺🎤👏👏👏\u0026quot;\nconcert.indexesOf(ptnr: \u0026quot;🎻🎷\u0026quot;) // Output: [6]\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003edna\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s\"\u003e\"\u003c/span\u003e\u003cspan class=\"pl-s\"\u003eACCCGGTTTTAAAGAACCACCATAAGATATAGACAGATATAGGACAGATATAGAGACAAAACCCCATACCCCAATATTTTTTTGGGGAGAAAAACACCACAGATAGATACACAGACTACACGAGATACGACATACAGCAGCATAACGACAACAGCAGATAGACGATCATAACAGCAATCAGACCGAGCGCAGCAGCTTTTAAGCACCAGCCCCACAAAAAACGACAATFATCATCATATACAGACGACGACACGACATATCACACGACAGCATA\u003c/span\u003e\u003cspan class=\"pl-s\"\u003e\"\u003c/span\u003e\ndna\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eindexesOf\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003eptnr\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-s\"\u003e\"\u003c/span\u003e\u003cspan class=\"pl-s\"\u003eCATA\u003c/span\u003e\u003cspan class=\"pl-s\"\u003e\"\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e // Output: [20, 64, 130, 140, 166, 234, 255, 270]\n\n\u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003econcert\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s\"\u003e\"\u003c/span\u003e\u003cspan class=\"pl-s\"\u003e🎼🎹🎹🎸🎸🎻🎻🎷🎺🎤👏👏👏\u003c/span\u003e\u003cspan class=\"pl-s\"\u003e\"\u003c/span\u003e\nconcert\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eindexesOf\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003eptnr\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-s\"\u003e\"\u003c/span\u003e\u003cspan class=\"pl-s\"\u003e🎻🎷\u003c/span\u003e\u003cspan class=\"pl-s\"\u003e\"\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e // Output: [6]\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThe \u003ca href=\"https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm\" rel=\"nofollow\"\u003eKnuth-Morris-Pratt algorithm\u003c/a\u003e is considered one of the best algorithms for solving the pattern matching problem. Although in practice \u003ca href=\"/zezzi/swift-algorithm-club/blob/Permutations/Boyer-Moore\"\u003eBoyer-Moore\u003c/a\u003e is usually preferred, the algorithm that we will introduce is simpler, and has the same (linear) running time.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThe idea behind the algorithm is not too different from the \u003ca href=\"/zezzi/swift-algorithm-club/blob/Permutations/Brute-Force%20String%20Search\"\u003enaive string search\u003c/a\u003e procedure. As it, Knuth-Morris-Pratt aligns the text with the pattern and goes with character comparisons from left to right. But, instead of making a shift of one character when a mismatch occurs, it uses a more intelligent way to move the pattern along the text. In fact, the algorithm features a pattern pre-processing stage where it acquires all the informations that will make the algorithm skip redundant comparisons, resulting in larger shifts.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThe pre-processing stage produces an array (called \u003ccode\u003esuffixPrefix\u003c/code\u003e in the code) of integers in which every element \u003ccode\u003esuffixPrefix[i]\u003c/code\u003e records the length of the longest proper suffix of \u003ccode\u003eP[0...i]\u003c/code\u003e (where \u003ccode\u003eP\u003c/code\u003e is the pattern) that matches a prefix of \u003ccode\u003eP\u003c/code\u003e. In other words, \u003ccode\u003esuffixPrefix[i]\u003c/code\u003e is the longest proper substring of \u003ccode\u003eP\u003c/code\u003e that ends at position \u003ccode\u003ei\u003c/code\u003e and that is a prefix of \u003ccode\u003eP\u003c/code\u003e. Just a quick example. Consider \u003ccode\u003eP = \"abadfryaabsabadffg\"\u003c/code\u003e, then \u003ccode\u003esuffixPrefix[4] = 0\u003c/code\u003e, \u003ccode\u003esuffixPrefix[9] = 2\u003c/code\u003e, \u003ccode\u003esuffixPrefix[14] = 4\u003c/code\u003e.\nThere are different ways to obtain the values of \u003ccode\u003eSuffixPrefix\u003c/code\u003e array. We will use the method based on the \u003ca href=\"/zezzi/swift-algorithm-club/blob/Permutations/Z-Algorithm\"\u003eZ-Algorithm\u003c/a\u003e. This function takes in input the pattern and produces an array of integers. Each element represents the length of the longest substring starting at position \u003ccode\u003ei\u003c/code\u003e of \u003ccode\u003eP\u003c/code\u003e and that matches a prefix of \u003ccode\u003eP\u003c/code\u003e. You can notice that the two arrays are similar, they record the same informations but on the different places. We only have to find a method to map \u003ccode\u003eZ[i]\u003c/code\u003e to \u003ccode\u003esuffixPrefix[j]\u003c/code\u003e. It is not that difficult and this is the code that will do for us:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"for patternIndex in (1 ..\u0026lt; patternLength).reversed() {\n textIndex = patternIndex + zeta![patternIndex] - 1\n suffixPrefix[textIndex] = zeta![patternIndex]\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003efor\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003epatternIndex\u003c/span\u003e \u003cspan class=\"pl-k\"\u003ein\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e..\u0026lt;\u003c/span\u003e patternLength\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003ereversed\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n textIndex \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e patternIndex \u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e zeta!\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003epatternIndex\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n \u003cspan class=\"pl-en\"\u003esuffixPrefix\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003etextIndex\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e zeta!\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003epatternIndex\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\n\u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eWe are simply computing the index of the end of the substring starting at position \u003ccode\u003ei\u003c/code\u003e (as we know matches a prefix of \u003ccode\u003eP\u003c/code\u003e). The element of \u003ccode\u003esuffixPrefix\u003c/code\u003e at that index then it will be set with the length of the substring.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eOnce the shift-array \u003ccode\u003esuffixPrefix\u003c/code\u003e is ready we can begin with pattern search stage. The algorithm first attempts to compare the characters of the text with those of the pattern. If it succeeds, it goes on until a mismatch occurs. When it happens, it checks if an occurrence of the pattern is present (and reports it). Otherwise, if no comparisons are made then the text cursor is moved forward, else the pattern is shifted to the right. The shift's amount is based on the \u003ccode\u003esuffixPrefix\u003c/code\u003e array, and it guarantees that the prefix \u003ccode\u003eP[0...suffixPrefix[i]]\u003c/code\u003e will match its opposing substring in the text. In this way, shifts of more than one character are often made and lot of comparisons can be avoided, saving a lot of time.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eHere is the code of the Knuth-Morris-Pratt algorithm:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"extension String {\n\n func indexesOf(ptnr: String) -\u0026gt; [Int]? {\n\n let text = Array(self.characters)\n let pattern = Array(ptnr.characters)\n\n let textLength: Int = text.count\n let patternLength: Int = pattern.count\n\n guard patternLength \u0026gt; 0 else {\n return nil\n }\n\n var suffixPrefix: [Int] = [Int](repeating: 0, count: patternLength)\n var textIndex: Int = 0\n var patternIndex: Int = 0\n var indexes: [Int] = [Int]()\n\n /* Pre-processing stage: computing the table for the shifts (through Z-Algorithm) */\n let zeta = ZetaAlgorithm(ptnr: ptnr)\n\n for patternIndex in (1 ..\u0026lt; patternLength).reversed() {\n textIndex = patternIndex + zeta![patternIndex] - 1\n suffixPrefix[textIndex] = zeta![patternIndex]\n }\n\n /* Search stage: scanning the text for pattern matching */\n textIndex = 0\n patternIndex = 0\n\n while textIndex + (patternLength - patternIndex - 1) \u0026lt; textLength {\n\n while patternIndex \u0026lt; patternLength \u0026amp;\u0026amp; text[textIndex] == pattern[patternIndex] {\n textIndex = textIndex + 1\n patternIndex = patternIndex + 1\n }\n\n if patternIndex == patternLength {\n indexes.append(textIndex - patternIndex)\n }\n\n if patternIndex == 0 {\n textIndex = textIndex + 1\n } else {\n patternIndex = suffixPrefix[patternIndex - 1]\n }\n }\n\n guard !indexes.isEmpty else {\n return nil\n }\n return indexes\n }\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003eextension\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eString\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n\n \u003cspan class=\"pl-en\"\u003efunc\u003c/span\u003e indexesOf\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003eptnr\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eString\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003e\u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e\u003cspan class=\"pl-c1\"\u003e?\u003c/span\u003e\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etext\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eArray\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-smi\"\u003eself\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003echaracters\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003epattern\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eArray\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003eptnr\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003echaracters\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etextLength\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e text\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003ecount\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003epatternLength\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e pattern\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003ecount\n\n \u003cspan class=\"pl-k\"\u003eguard\u003c/span\u003e patternLength \u003cspan class=\"pl-c1\"\u003e\u0026gt;\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003enil\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003esuffixPrefix\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003e\u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003eInt\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003erepeating\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e count\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e patternLength\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etextIndex\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003epatternIndex\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eindexes\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003e\u003cspan class=\"pl-smi\"\u003eInt\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003eInt\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n\n /* Pre-processing stage: computing the table for the shifts (through Z-Algorithm) */\n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ezeta\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eZetaAlgorithm\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003eptnr\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e ptnr\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n\n \u003cspan class=\"pl-k\"\u003efor\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003epatternIndex\u003c/span\u003e \u003cspan class=\"pl-k\"\u003ein\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e..\u0026lt;\u003c/span\u003e patternLength\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003ereversed\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n textIndex \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e patternIndex \u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e zeta!\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003epatternIndex\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n \u003cspan class=\"pl-en\"\u003esuffixPrefix\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003etextIndex\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e zeta!\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003epatternIndex\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n\n /* Search stage: scanning the text for pattern matching */\n textIndex \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\n patternIndex \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\n\n \u003cspan class=\"pl-k\"\u003ewhile\u003c/span\u003e textIndex \u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003epatternLength \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e patternIndex \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e textLength \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n\n \u003cspan class=\"pl-k\"\u003ewhile\u003c/span\u003e patternIndex \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e patternLength \u0026amp;\u0026amp; \u003cspan class=\"pl-en\"\u003etext\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003etextIndex\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-en\"\u003epattern\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003epatternIndex\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n textIndex \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e textIndex \u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n patternIndex \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e patternIndex \u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e patternIndex \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e patternLength \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n indexes\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eappend\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003etextIndex \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e patternIndex\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e patternIndex \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n textIndex \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e textIndex \u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n patternIndex \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003esuffixPrefix\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003epatternIndex \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n\n \u003cspan class=\"pl-k\"\u003eguard\u003c/span\u003e !indexes\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003eisEmpty \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003enil\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e indexes\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n\u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eLet's make an example reasoning with the code above. Let's consider the string \u003ccode\u003eP = ACTGACTA\"\u003c/code\u003e, the consequentially obtained \u003ccode\u003esuffixPrefix\u003c/code\u003e array equal to \u003ccode\u003e[0, 0, 0, 0, 0, 0, 3, 1]\u003c/code\u003e, and the text \u003ccode\u003eT = \"GCACTGACTGACTGACTAG\"\u003c/code\u003e. The algorithm begins with the text and the pattern aligned like below. We have to compare \u003ccode\u003eT[0]\u003c/code\u003e with \u003ccode\u003eP[0]\u003c/code\u003e.\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\" 1 \n 0123456789012345678\ntext: GCACTGACTGACTGACTAG\ntextIndex: ^\npattern: ACTGACTA\npatternIndex: ^\n x\nsuffixPrefix: 00000031\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e 1 \n 0123456789012345678\ntext: GCACTGACTGACTGACTAG\ntextIndex: ^\npattern: ACTGACTA\npatternIndex: ^\n x\nsuffixPrefix: 00000031\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eWe have a mismatch and we move on comparing \u003ccode\u003eT[1]\u003c/code\u003e and \u003ccode\u003eP[0]\u003c/code\u003e. We have to check if a pattern occurrence is present but there is not. So, we have to shift the pattern right and by doing so we have to check \u003ccode\u003esuffixPrefix[1 - 1]\u003c/code\u003e. Its value is \u003ccode\u003e0\u003c/code\u003e and we restart by comparing \u003ccode\u003eT[1]\u003c/code\u003e with \u003ccode\u003eP[0]\u003c/code\u003e. Again a mismath occurs, so we go on with \u003ccode\u003eT[2]\u003c/code\u003e and \u003ccode\u003eP[0]\u003c/code\u003e.\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\" 1 \n 0123456789012345678\ntext: GCACTGACTGACTGACTAG\ntextIndex: ^\npattern: ACTGACTA\npatternIndex: ^\nsuffixPrefix: 00000031\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e 1 \n 0123456789012345678\ntext: GCACTGACTGACTGACTAG\ntextIndex: ^\npattern: ACTGACTA\npatternIndex: ^\nsuffixPrefix: 00000031\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThis time we have a match. And it continues until position \u003ccode\u003e8\u003c/code\u003e. Unfortunately the length of the match is not equal to the pattern length, we cannot report an occurrence. But we are still lucky because we can use the values computed in the \u003ccode\u003esuffixPrefix\u003c/code\u003e array now. In fact, the length of the match is \u003ccode\u003e7\u003c/code\u003e, and if we look at the element \u003ccode\u003esuffixPrefix[7 - 1]\u003c/code\u003e we discover that is \u003ccode\u003e3\u003c/code\u003e. This information tell us that that the prefix of \u003ccode\u003eP\u003c/code\u003e matches the suffix of the susbtring \u003ccode\u003eT[0...8]\u003c/code\u003e. So the \u003ccode\u003esuffixPrefix\u003c/code\u003e array guarantees us that the two substring match and that we do not have to compare their characters, so we can shift right the pattern for more than one character!\nThe comparisons restart from \u003ccode\u003eT[9]\u003c/code\u003e and \u003ccode\u003eP[3]\u003c/code\u003e.\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\" 1 \n 0123456789012345678\ntext: GCACTGACTGACTGACTAG\ntextIndex: ^\npattern: ACTGACTA\npatternIndex: ^\nsuffixPrefix: 00000031\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e 1 \n 0123456789012345678\ntext: GCACTGACTGACTGACTAG\ntextIndex: ^\npattern: ACTGACTA\npatternIndex: ^\nsuffixPrefix: 00000031\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThey match so we continue the compares until position \u003ccode\u003e13\u003c/code\u003e where a misatch occurs beetwen charcter \u003ccode\u003eG\u003c/code\u003e and \u003ccode\u003eA\u003c/code\u003e. Just like before, we are lucky and we can use the \u003ccode\u003esuffixPrefix\u003c/code\u003e array to shift right the pattern.\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\" 1 \n 0123456789012345678\ntext: GCACTGACTGACTGACTAG\ntextIndex: ^\npattern: ACTGACTA\npatternIndex: ^\nsuffixPrefix: 00000031\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e 1 \n 0123456789012345678\ntext: GCACTGACTGACTGACTAG\ntextIndex: ^\npattern: ACTGACTA\npatternIndex: ^\nsuffixPrefix: 00000031\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eAgain, we have to compare. But this time the comparisons finally take us to an occurrence, at position \u003ccode\u003e17 - 7 = 10\u003c/code\u003e.\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\" 1 \n 0123456789012345678\ntext: GCACTGACTGACTGACTAG\ntextIndex: ^\npattern: ACTGACTA\npatternIndex: ^\nsuffixPrefix: 00000031\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e 1 \n 0123456789012345678\ntext: GCACTGACTGACTGACTAG\ntextIndex: ^\npattern: ACTGACTA\npatternIndex: ^\nsuffixPrefix: 00000031\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThe algorithm than tries to compare \u003ccode\u003eT[18]\u003c/code\u003e with \u003ccode\u003eP[1]\u003c/code\u003e (because we used the element \u003ccode\u003esuffixPrefix[8 - 1] = 1\u003c/code\u003e) but it fails and at the next iteration it ends its work.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThe pre-processing stage involves only the pattern. The running time of the Z-Algorithm is linear and takes \u003ccode\u003eO(n)\u003c/code\u003e, where \u003ccode\u003en\u003c/code\u003e is the length of the pattern \u003ccode\u003eP\u003c/code\u003e. After that, the search stage does not \"overshoot\" the length of the text \u003ccode\u003eT\u003c/code\u003e (call it \u003ccode\u003em\u003c/code\u003e). It can be be proved that number of comparisons of the search stage is bounded by \u003ccode\u003e2 * m\u003c/code\u003e. The final running time of the Knuth-Morris-Pratt algorithm is \u003ccode\u003eO(n + m)\u003c/code\u003e.\u003c/p\u003e\n\u003cblockquote\u003e\n\u003cp dir=\"auto\"\u003e\u003cstrong\u003eNote:\u003c/strong\u003e To execute the code in the \u003ca href=\"/zezzi/swift-algorithm-club/blob/Permutations/Knuth-Morris-Pratt/KnuthMorrisPratt.swift\"\u003eKnuthMorrisPratt.swift\u003c/a\u003e you have to copy the \u003ca href=\"/zezzi/swift-algorithm-club/blob/Permutations/Z-Algorithm/ZAlgorithm.swift\"\u003eZAlgorithm.swift\u003c/a\u003e file contained in the \u003ca href=\"/zezzi/swift-algorithm-club/blob/Permutations/Z-Algorithm\"\u003eZ-Algorithm\u003c/a\u003e folder. The \u003ca href=\"/zezzi/swift-algorithm-club/blob/Permutations/Knuth-Morris-Pratt/KnuthMorrisPratt.playground\"\u003eKnuthMorrisPratt.playground\u003c/a\u003e already includes the definition of the \u003ccode\u003eZeta\u003c/code\u003e function.\u003c/p\u003e\n\u003c/blockquote\u003e\n\u003cp dir=\"auto\"\u003eCredits: This code is bas
5342
ed on the handbook \u003ca href=\"https://books.google.it/books/about/Algorithms_on_Strings_Trees_and_Sequence.html?id=Ofw5w1yuD8kC\u0026amp;redir_esc=y\" rel=\"nofollow\"\u003e\"Algorithm on String, Trees and Sequences: Computer Science and Computational Biology\"\u003c/a\u003e by Dan Gusfield, Cambridge University Press, 1997.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003cem\u003eWritten for Swift Algorithm Club by Matteo Dunnhofer\u003c/em\u003e\u003c/p\u003e\n\u003c/article\u003e","errorMessage":null,"headerInfo":{"toc":[{"level":1,"text":"Knuth-Morris-Pratt String Search","anchor":"knuth-morris-pratt-string-search","htmlText":"Knuth-Morris-Pratt String Search"}],"siteNavLoginPath":"/login?return_to=https%3A%2F%2Fgithub.com%2Fzezzi%2Fswift-algorithm-club%2Ftree%2FPermutations%2FKnuth-Morris-Pratt"}},"totalCount":3,"showBranchInfobar":true},"fileTree":{"":{"items":[{"name":".github","path":".github","contentType":"directory"},{"name":"3Sum and 4Sum","path":"3Sum and 4Sum","contentType":"directory"},{"name":"AVL Tree","path":"AVL Tree","contentType":"directory"},{"name":"All-Pairs Shortest Paths","path":"All-Pairs Shortest Paths","contentType":"directory"},{"name":"Array2D","path":"Array2D","contentType":"directory"},{"name":"B-Tree","path":"B-Tree","contentType":"directory"},{"name":"Binary Search Tree","path":"Binary Search Tree","contentType":"directory"},{"name":"Binary Search","path":"Binary Search","contentType":"directory"},{"name":"Binary Tree","path":"Binary Tree","contentType":"directory"},{"name":"Bit Set","path":"Bit Set","contentType":"directory"},{"name":"Bloom Filter","path":"Bloom Filter","contentType":"directory"},{"name":"Bounded Priority Queue","path":"Bounded Priority Queue","contentType":"directory"},{"name":"Boyer-Moore-Horspool","path":"Boyer-Moore-Horspool","contentType":"directory"},{"name":"Breadth-First Search","path":"Breadth-First Search","contentType":"directory"},{"name":"Brute-Force String Search","path":"Brute-Force String Search","contentType":"directory"},{"name":"Bubble Sort","path":"Bubble Sort","contentType":"directory"},{"name":"Bucket Sort","path":"Bucket Sort","contentType":"directory"},{"name":"Comb Sort","path":"Comb Sort","contentType":"directory"},{"name":"Combinatorics","path":"Combinatorics","contentType":"directory"},{"name":"Convex Hull","path":"Convex Hull","contentType":"directory"},{"name":"Count Occurrences","path":"Count Occurrences","contentType":"directory"},{"name":"Counting Sort","path":"Counting Sort","contentType":"directory"},{"name":"Depth-First Search","path":"Depth-First Search","contentType":"directory"},{"name":"Deque","path":"Deque","contentType":"directory"},{"name":"Dijkstra Algorithm","path":"Dijkstra Algorithm","contentType":"directory"},{"name":"DiningPhilosophers","path":"DiningPhilosophers","contentType":"directory"},{"name":"Egg Drop Problem","path":"Egg Drop Problem","contentType":"directory"},{"name":"Encode and Decode Tree","path":"Encode and Decode Tree","contentType":"directory"},{"name":"Fixed Size Array","path":"Fixed Size Array","contentType":"directory"},{"name":"Fizz Buzz","path":"Fizz Buzz","contentType":"directory"},{"name":"GCD","path":"GCD","contentType":"directory"},{"name":"Graph","path":"Graph","contentType":"directory"},{"name":"Hash Set","path":"Hash Set","contentType":"directory"},{"name":"Hash Table","path":"Hash Table","contentType":"directory"},{"name":"Hashed Heap","path":"Hashed Heap","contentType":"directory"},{"name":"HaversineDistance","path":"HaversineDistance","contentType":"directory"},{"name":"Heap Sort","path":"Heap Sort","contentType":"directory"},{"name":"Heap","path":"Heap","contentType":"directory"},{"name":"Huffman Coding","path":"Huffman Coding","contentType":"directory"},{"name":"Images","path":"Images","contentType":"directory"},{"name":"Insertion Sort","path":"Insertion Sort","contentType":"directory"},{"name":"K-Means","path":"K-Means","contentType":"directory"},{"name":"Karatsuba Multiplication","path":"Karatsuba Multiplication","contentType":"directory"},{"name":"Knuth-Morris-Pratt","path":"Knuth-Morris-Pratt","contentType":"directory"},{"name":"Kth Largest Element","path":"Kth Largest Element","contentType":"directory"},{"name":"LRU Cache","path":"LRU Cache","contentType":"directory"},{"name":"Linear Regression","path":"Linear Regression","contentType":"directory"},{"name":"Linear Search","path":"Linear Search","contentType":"directory"},{"name":"Linked List","path":"Linked List","contentType":"directory"},{"name":"Longest Common Subsequence","path":"Longest Common Subsequence","contentType":"directory"},{"name":"Merge Sort","path":"Merge Sort","contentType":"directory"},{"name":"Miller-Rabin Primality Test","path":"Miller-Rabin Primality Test","contentType":"directory"},{"name":"Minimum Edit Distance","path":"Minimum Edit Distance","contentType":"directory"},{"name":"Minimum Spanning Tree (Unweighted)","path":"Minimum Spanning Tree (Unweighted)","contentType":"directory"},{"name":"Minimum Spanning Tree","path":"Minimum Spanning Tree","contentType":"directory"},{"name":"MinimumCoinChange","path":"MinimumCoinChange","contentType":"directory"},{"name":"Monty Hall Problem","path":"Monty Hall Problem","contentType":"directory"},{"name":"Multiset","path":"Multiset","contentType":"directory"},{"name":"Naive Bayes Classifier","path":"Naive Bayes Classifier","contentType":"directory"},{"name":"Octree","path":"Octree","contentType":"directory"},{"name":"Ordered Array","path":"Ordered Array","contentType":"directory"},{"name":"Ordered Set","path":"Ordered Set","contentType":"directory"},{"name":"Palindromes","path":"Palindromes","contentType":"directory"},{"name":"Permutations","path":"Permutations","contentType":"directory"},{"name":"Priority Queue","path":"Priority Queue","contentType":"directory"},{"name":"QuadTree","path":"QuadTree","contentType":"directory"},{"name":"Queue","path":"Queue","contentType":"directory"},{"name":"Quicksort","path":"Quicksort","contentType":"directory"},{"name":"Rabin-Karp","path":"Rabin-Karp","contentType":"directory"},{"name":"Radix Sort","path":"Radix Sort","contentType":"directory"},{"name":"Radix Tree","path":"Radix Tree","contentType":"directory"},{"name":"Red-Black Tree","path":"Red-Black Tree","contentType":"directory"},{"name":"Ring Buffer","path":"Ring Buffer","contentType":"directory"},{"name":"Rootish Array Stack","path":"Rootish Array Stack","contentType":"directory"},{"name":"Run-Length Encoding","path":"Run-Length Encoding","contentType":"directory"},{"name":"Segment Tree","path":"Segment Tree","contentType":"directory"},{"name":"Select Minimum Maximum","path":"Select Minimum Maximum","contentType":"directory"},{"name":"Selection Sampling","path":"Selection Sampling","contentType":"directory"},{"name":"Selection Sort","path":"Selection Sort","contentType":"directory"},{"name":"Set Cover (Unweighted)","path":"Set Cover (Unweighted)","contentType":"directory"},{"name":"Shell Sort","path":"Shell Sort","contentType":"directory"},{"name":"Shortest Path (Unweighted)","path":"Shortest Path (Unweighted)","contentType":"directory"},{"name":"Shuffle","path":"Shuffle","contentType":"directory"},{"name":"Shunting Yard","path":"Shunting Yard","contentType":"directory"},{"name":"Single-Source Shortest Paths (Weighted)","path":"Single-Source Shortest Paths (Weighted)","contentType":"directory"},{"name":"Singly Linked List","path":"Singly Linked List","contentType":"directory"},{"name":"Skip-List","path":"Skip-List","contentType":"directory"},{"name":"Slow Sort","path":"Slow Sort","contentType":"directory"},{"name":"Sorted Set","path":"Sorted Set","contentType":"directory"},{"name":"Splay Tree","path":"Splay Tree","contentType":"directory"},{"name":"Stack","path":"Stack","contentType":"directory"},{"name":"Strassen Matrix Multiplication","path":"Strassen Matrix Multiplication","contentType":"directory"},{"name":"Ternary Search Tree","path":"Ternary Search Tree","contentType":"directory"},{"name":"Threaded Binary Tree","path":"Threaded Binary Tree","contentType":"directory"},{"name":"Topological Sort","path":"Topological Sort","contentType":"directory"},{"name":"Treap","path":"Treap","contentType":"directory"},{"name":"Tree","path":"Tree","contentType":"directory"},{"name":"Trie","path":"Trie","contentType":"directory"},{"name":"Two-Sum Problem","path":"Two-Sum Problem","contentType":"directory"},{"name":"Union-Find","path":"Union-Find","contentType":"directory"},{"name":"Z-Algorithm","path":"Z-Algorithm","contentType":"directory"},{"name":"swift-algorithm-club.xcworkspace","path":"swift-algorithm-club.xcworkspace","contentType":"directory"},{"name":".gitignore","path":".gitignore","contentType":"file"},{"name":".swiftlint.yml","path":".swiftlint.yml","contentType":"file"},{"name":".travis.yml","path":".travis.yml","contentType":"file"},{"name":"Algorithm Design.markdown","path":"Algorithm Design.markdown","contentType":"file"},{"name":"Big-O Notation.markdown","path":"Big-O Notation.markdown","contentType":"file"},{"name":"LICENSE.txt","path":"LICENSE.txt","contentType":"file"},{"name":"README.markdown","path":"README.markdown","contentType":"file"},{"name":"Under Construction.markdown","path":"Under Construction.markdown","contentType":"file"},{"name":"What are Algorithms.markdown","path":"What are Algorithms.markdown","contentType":"file"},{"name":"Why Algorithms.markdown","path":"Why Algorithms.markdown","contentType":"file"},{"name":"gfm-render.sh","path":"gfm-render.sh","contentType":"file"},{"name":"install_swiftlint.sh","path":"install_swiftlint.sh","contentType":"file"}],"totalCount":114}},"fileTreeProcessingTime":4.899882000000001,"foldersToFetch":[],"treeExpanded":true,"symbolsExpanded":false,"csrf_tokens":{"/zezzi/swift-algorithm-club/branches":{"post":"20tPxvaQmWH8oFp8xLRua0RI3-U7R86fArAspGn6uZ_K1CvJoqkQK-GPIKtehl269RLhuAJUnaICtmiWubKUXA"},"/zezzi/swift-algorithm-club/branches/fetch_and_merge/Permutations":{"post":"sTCRf-n2o8yoQu-dZyZMY7EmojF57NlRKRGSd-7A-My0y7cvl9g1Ww22T3m8D3Ny4CRjyxzcm-L9of060PQAaQ"},"/zezzi/swift-algorithm-club/branches/fetch_and_merge/Permutations?discard_changes=true":{"post":"yJ-G5TV5c_EDpgWDf2Ovr0ZP398mryHL34oSZ1UMLtvNZKC1S1flZqZSpWekSpC-F00eJUOfY3gLOn0qazjWfg"}}},"title":"swift-algorithm-club/Knuth-Morris-Pratt at Permutations · zezzi/swift-algorithm-club","appPayload":{"helpUrl":"https://docs.github.com","findFileWorkerPath":"/assets-cdn/worker/find-file-worker-263cab1760dd.js","findInFileWorkerPath":"/assets-cdn/worker/find-in-file-worker-1b17b3e7786a.js","githubDevUrl":null,"enabled_features":{"code_nav_ui_events":false,"react_blob_overlay":false,"accessible_code_button":true}}}