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":"Z-Algorithm","repo":{"id":245351143,"defaultBranch":"master","name":"swift-algorithm-club","ownerLogin":"rreballos","currentUserCanPush":false,"isFork":true,"isEmpty":false,"createdAt":"2020-03-06T06:59:16.000Z","ownerAvatar":"https://avatars.githubusercontent.com/u/1049202?v=4","public":true,"private":false,"isOrgOwned":false},"currentUser":null,"refInfo":{"name":"master","listCacheKey":"v0:1615943933.75875","canEdit":false,"refType":"branch","currentOid":"c22182f0d0b7708380a152640401fe873a705c20"},"tree":{"items":[{"name":"ZetaAlgorithm.playground","path":"Z-Algorithm/ZetaAlgorithm.playground","contentType":"directory"},{"name":"README.markdown","path":"Z-Algorithm/README.markdown","contentType":"file"},{"name":"ZAlgorithm.swift","path":"Z-Algorithm/ZAlgorithm.swift","contentType":"file"},{"name":"ZetaAlgorithm.swift","path":"Z-Algorithm/ZetaAlgorithm.swift","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\"\u003eZ-Algorithm String Search\u003c/h1\u003e\u003ca id=\"user-content-z-algorithm-string-search\" class=\"anchor\" aria-label=\"Permalink: Z-Algorithm String Search\" href=\"#z-algorithm-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 simple 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 str = \u0026quot;Hello, playground!\u0026quot;\nstr.indexesOf(pattern: \u0026quot;ground\u0026quot;) // Output: [11]\n\nlet traffic = \u0026quot;🚗🚙🚌🚕🚑🚐🚗🚒🚚🚎🚛🚐🏎🚜🚗🏍🚒🚲🚕🚓🚌🚑\u0026quot;\ntraffic.indexesOf(pattern: \u0026quot;🚑\u0026quot;) // Output: [4, 21]\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003estr\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s\"\u003e\"\u003c/span\u003e\u003cspan class=\"pl-s\"\u003eHello, playground!\u003c/span\u003e\u003cspan class=\"pl-s\"\u003e\"\u003c/span\u003e\nstr\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eindexesOf\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003epattern\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-s\"\u003e\"\u003c/span\u003e\u003cspan class=\"pl-s\"\u003eground\u003c/span\u003e\u003cspan class=\"pl-s\"\u003e\"\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e // Output: [11]\n\n\u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etraffic\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\ntraffic\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eindexesOf\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003epattern\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: [4, 21]\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eMany string search algorithms use a pre-processing function to compute a table that will be used in successive stage. This table can save some time during the pattern search stage because it allows to avoid un-needed characters comparisons. The \u003ca href=\"/rreballos/swift-algorithm-club/blob/master/Z-Algorithm\"\u003eZ-Algorithm\u003c/a\u003e is one of these functions. It borns as a pattern pre-processing function (this is its role in the \u003ca href=\"/rreballos/swift-algorithm-club/blob/master/Knuth-Morris-Pratt\"\u003eKnuth-Morris-Pratt algorithm\u003c/a\u003e and others) but, just like we will show here, it can be used also as a single string search algorithm.\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch3 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eZ-Algorithm as pattern pre-processor\u003c/h3\u003e\u003ca id=\"user-content-z-algorithm-as-pattern-pre-processor\" class=\"anchor\" aria-label=\"Permalink: Z-Algorithm as pattern pre-processor\" href=\"#z-algorithm-as-pattern-pre-processor\"\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\"\u003eAs we said, the Z-Algorithm is foremost an algorithm that process a pattern in order to calculate a skip-comparisons-table.\nThe computation of the Z-Algorithm over a pattern \u003ccode\u003eP\u003c/code\u003e produces an array (called \u003ccode\u003eZ\u003c/code\u003e in the literature) of integers in which each element, call it \u003ccode\u003eZ[i]\u003c/code\u003e, represents the length of the longest substring of \u003ccode\u003eP\u003c/code\u003e that starts at \u003ccode\u003ei\u003c/code\u003e and matches a prefix of \u003ccode\u003eP\u003c/code\u003e. In simpler words, \u003ccode\u003eZ[i]\u003c/code\u003e records the longest prefix of \u003ccode\u003eP[i...|P|]\u003c/code\u003e that matches a prefix of \u003ccode\u003eP\u003c/code\u003e. As an example, let's consider \u003ccode\u003eP = \"ffgtrhghhffgtggfredg\"\u003c/code\u003e. We have that \u003ccode\u003eZ[5] = 0 (f...h...)\u003c/code\u003e, \u003ccode\u003eZ[9] = 4 (ffgtr...ffgtg...)\u003c/code\u003e and \u003ccode\u003eZ[15] = 1 (ff...fr...)\u003c/code\u003e.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eBut how do we compute \u003ccode\u003eZ\u003c/code\u003e? Before we describe the algorithm we must indroduce the concept of Z-box. A Z-box is a pair \u003ccode\u003e(left, right)\u003c/code\u003e used during the computation that records the substring of maximal length that occurs also as a prefix of \u003ccode\u003eP\u003c/code\u003e. The two indices \u003ccode\u003eleft\u003c/code\u003e and \u003ccode\u003eright\u003c/code\u003e represent, respectively, the left-end index and the right-end index of this substring.\nThe definition of the Z-Algorithm is inductive and it computes the elements of the array for every position \u003ccode\u003ek\u003c/code\u003e in the pattern, starting from \u003ccode\u003ek = 1\u003c/code\u003e. The following values (\u003ccode\u003eZ[k + 1]\u003c/code\u003e, \u003ccode\u003eZ[k + 2]\u003c/code\u003e, ...) are computed after \u003ccode\u003eZ[k]\u003c/code\u003e. The idea behind the algorithm is that previously computed values can speed up the calculus of \u003ccode\u003eZ[k + 1]\u003c/code\u003e, avoiding some character comparisons that were already done before. Consider this example: suppose we are at iteration \u003ccode\u003ek = 100\u003c/code\u003e, so we are analyzing position \u003ccode\u003e100\u003c/code\u003e of the pattern. All the values between \u003ccode\u003eZ[1]\u003c/code\u003e and \u003ccode\u003eZ[99]\u003c/code\u003e were correctly computed and \u003ccode\u003eleft = 70\u003c/code\u003e and \u003ccode\u003eright = 120\u003c/code\u003e. This means that there is a substring of length \u003ccode\u003e51\u003c/code\u003e starting at position \u003ccode\u003e70\u003c/code\u003e and ending at position \u003ccode\u003e120\u003c/code\u003e that matches the prefix of the pattern/string we are considering. Reasoning on it a little bit we can say that the substring of length \u003ccode\u003e21\u003c/code\u003e starting at position \u003ccode\u003e100\u003c/code\u003e matches the substring of length \u003ccode\u003e21\u003c/code\u003e starting at position \u003ccode\u003e30\u003c/code\u003e of the pattern (because we are inside a substring that matches a prefix of the pattern). So we can use \u003ccode\u003eZ[30]\u003c/code\u003e to compute \u003ccode\u003eZ[100]\u003c/code\u003e without additional character comparisons.\nThis a simple description of the idea that is behind this algorithm. There are a few cases to manage when the use of pre-computed values cannot be directly applied and some comparisons are to be made.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eHere is the code of the function that computes the Z-array:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"func ZetaAlgorithm(ptrn: String) -\u0026gt; [Int]? {\n let pattern = Array(ptrn)\n let patternLength: Int = pattern.count\n\n guard patternLength \u0026gt; 0 else {\n return nil\n }\n\n var zeta: [Int] = [Int](repeating: 0, count: patternLength)\n\n var left: Int = 0\n var right: Int = 0\n var k_1: Int = 0\n var betaLength: Int = 0\n var textIndex: Int = 0\n var patternIndex: Int = 0\n\n for k in 1 ..\u0026lt; patternLength {\n if k \u0026gt; right { // Outside a Z-box: compare the characters until mismatch\n patternIndex = 0\n\n while k + patternIndex \u0026lt; patternLength \u0026amp;\u0026amp;\n pattern[k + patternIndex] == pattern[patternIndex] {\n patternIndex = patternIndex + 1\n }\n\n zeta[k] = patternIndex\n\n if zeta[k] \u0026gt; 0 {\n left = k\n right = k + zeta[k] - 1\n }\n } else { // Inside a Z-box\n k_1 = k - left + 1\n betaLength = right - k + 1\n\n if zeta[k_1 - 1] \u0026lt; betaLength { // Entirely inside a Z-box: we can use the values computed before\n zeta[k] = zeta[k_1 - 1]\n } else if zeta[k_1 - 1] \u0026gt;= betaLength { // Not entirely inside a Z-box: we must proceed with comparisons too\n textIndex = betaLength\n patternIndex = right + 1\n\n while patternIndex \u0026lt; patternLength \u0026amp;\u0026amp; pattern[textIndex] == pattern[patternIndex] {\n textIndex = textIndex + 1\n patternIndex = patternIndex + 1\n }\n\n zeta[k] = patternIndex - k\n left = k\n right = patternIndex - 1\n }\n }\n }\n return zeta\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-en\"\u003efunc\u003c/span\u003e ZetaAlgorithm\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003eptrn\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 \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\u003eptrn\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\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\"\u003ezeta\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\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eleft\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\"\u003eright\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\"\u003ek_1\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\"\u003ebetaLength\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\"\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\n \u003cspan class=\"pl-k\"\u003efor\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ek\u003c/span\u003e \u003cspan class=\"pl-k\"\u003ein\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\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e k \u003cspan class=\"pl-c1\"\u003e\u0026gt;\u003c/span\u003e right \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e // Outside a Z-box: compare the characters until mismatch\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 k \u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e patternIndex \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e patternLength \u0026amp;\u0026amp;\n \u003cspan class=\"pl-en\"\u003epattern\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ek \u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e patternIndex\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 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-en\"\u003ezeta\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ek\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e patternIndex\n\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-en\"\u003ezeta\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ek\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e\u0026gt;\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n left \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e k\n right \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e k \u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e zeta\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ek\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-kos\"\u003e}\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 // Inside a Z-box\n k_1 \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e k \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e left \u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n betaLength \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e right \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e k \u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-en\"\u003ezeta\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ek_1 \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 betaLength \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e // Entirely inside a Z-box: we can use the values computed before\n \u003cspan class=\"pl-en\"\u003ezeta\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ek\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003ezeta\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ek_1 \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 \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-en\"\u003ezeta\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ek_1 \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\u0026gt;=\u003c/span\u003e betaLength \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e // Not entirely inside a Z-box: we must proceed with comparisons too\n textIndex \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e betaLength\n patternIndex \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e right \u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\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\"\u003epattern\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-en\"\u003ezeta\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ek\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e patternIndex \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e k\n left \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e k\n right \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 \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e zeta\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 = “abababbb\"\u003c/code\u003e. The algorithm begins with \u003ccode\u003ek = 1\u003c/code\u003e, \u003ccode\u003eleft = right = 0\u003c/code\u003e. So, no Z-box is \"active\" and thus, because \u003ccode\u003ek \u0026gt; right\u003c/code\u003e we start with the character comparisons beetwen \u003ccode\u003eP[1]\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=\" 01234567\nk: x\n abababbb\n x\nZ: 00000000\nleft: 0\nright: 0\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e 01234567\nk: x\n abababbb\n x\nZ: 00000000\nleft: 0\nright: 0\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eWe have a mismatch at the first comparison and so the substring starting at \u003ccode\u003eP[1]\u003c/code\u003e does not match a prefix of \u003ccode\u003eP\u003c/code\u003e. So, we put \u003ccode\u003eZ[1] = 0\u003c/code\u003e and let \u003ccode\u003eleft\u003c/code\u003e and \u003ccode\u003eright\u003c/code\u003e untouched. We begin another iteration with \u003ccode\u003ek = 2\u003c/code\u003e, we have \u003ccode\u003e2 \u0026gt; 0\u003c/code\u003e and again we start comparing characters \u003ccode\u003eP[2]\u003c/code\u003e with \u003ccode\u003eP[0]\u003c/code\u003e. This time the characters match and so we continue the comparisons until a mismatch occurs. It happens at position \u003ccode\u003e6\u003c/code\u003e. The characters matched are \u003ccode\u003e4\u003c/code\u003e, so we put \u003ccode\u003eZ[2] = 4\u003c/code\u003e and set \u003ccode\u003eleft = k = 2\u003c/code\u003e and \u003ccode\u003eright = k + Z[k] - 1 = 5\u003c/code\u003e. We have our first Z-box that is the substring \u003ccode\u003e\"abab\"\u003c/code\u003e (notice that it matches a prefix of \u003ccode\u003eP\u003c/code\u003e) starting at position \u003ccode\u003eleft = 2\u003c/code\u003e.\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\" 01234567\nk: x\n abababbb\n x\nZ: 00400000\nleft: 2\nright: 5\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e 01234567\nk: x\n abababbb\n x\nZ: 00400000\nleft: 2\nright: 5\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eWe then proceed with \u003ccode\u003ek = 3\u003c/code\u003e. We have \u003ccode\u003e3 \u0026lt;= 5\u003c/code\u003e. We are inside the Z-box previously found and inside a prefix of \u003ccode\u003eP\u003c/code\u003e. So we can look for a position that has a previously computed value. We calculate \u003ccode\u003ek_1 = k - left = 1\u003c/code\u003e that is the index of the prefix's character equal to \u003ccode\u003eP[k]\u003c/code\u003e. We check \u003ccode\u003eZ[1] = 0\u003c/code\u003e and \u003ccode\u003e0 \u0026lt; (right - k + 1 = 3)\u003c/code\u003e and we find that we are exactly inside the Z-box. We can use the previously computed value, so we put \u003ccode\u003eZ[3] = Z[1] = 0\u003c/code\u003e, \u003ccode\u003eleft\u003c/code\u003e and \u003ccode\u003eright\u003c/code\u003e remain unchanged.\nAt iteration \u003ccode\u003ek = 4\u003c/code\u003e we initially execute the \u003ccode\u003eelse\u003c/code\u003e branch of the outer \u003ccode\u003eif\u003c/code\u003e. Then in the inner \u003ccode\u003eif\u003c/code\u003e we have that \u003ccode\u003ek_1 = 2\u003c/code\u003e and \u003ccode\u003e(Z[2] = 4) \u0026gt;= 5 - 4 + 1\u003c/code\u003e. So, the substring \u003ccode\u003eP[k...r]\u003c/code\u003e matches for \u003ccode\u003eright - k + 1 = 2\u003c/code\u003e chars the prefix of \u003ccode\u003eP\u003c/code\u003e but it could not for the following characters. We must then compare the characters starting at \u003ccode\u003er + 1 = 6\u003c/code\u003e with those starting at \u003ccode\u003eright - k + 1 = 2\u003c/code\u003e. We have \u003ccode\u003eP[6] != P[2]\u003c/code\u003e and so we have to set \u003ccode\u003eZ[k] = 6 - 4 = 2\u003c/code\u003e, \u003ccode\u003eleft = 4\u003c/code\u003e and \u003ccode\u003eright = 5\u003c/code\u003e.\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\" 01234567\nk: x\n abababbb\n x\nZ: 00402000\nleft: 4\nright: 5\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e 01234567\nk: x\n abababbb\n x\nZ: 00402000\nleft: 4\nright: 5\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eWith iteration \u003ccode\u003ek = 5\u003c/code\u003e we have \u003ccode\u003ek \u0026lt;= right\u003c/code\u003e and then \u003ccode\u003e(Z[k_1] = 0) \u0026lt; (right - k + 1 = 1)\u003c/code\u003e and so we set \u003ccode\u003ez[k] = 0\u003c/code\u003e. In iteration \u003ccode\u003e6\u003c/code\u003e and \u003ccode\u003e7\u003c/code\u003e we execute the first branch of the outer \u003ccode\u003eif\u003c/code\u003e but we only have mismatches, so the algorithms terminates returning the Z-array as \u003ccode\u003eZ = [0, 0, 4, 0, 2, 0, 0, 0]\u003c/code\u003e.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThe Z-Algorithm runs in linear time. More specifically, the Z-Algorithm for a string \u003ccode\u003eP\u003c/code\u003e of size \u003ccode\u003en\u003c/code\u003e has a running time of \u003ccode\u003eO(n)\u003c/code\u003e.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eThe implementation of Z-Algorithm as string pre-processor is contained in the \u003ca href=\"/rreballos/swift-algorithm-club/blob/master/Z-Algorithm/ZAlgorithm.swift\"\u003eZAlgorithm.swift\u003c/a\u003e file.\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch3 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eZ-Algorithm as string search algorithm\u003c/h3\u003e\u003ca id=\"user-content-z-algorithm-as-string-search-algorithm\" class=\"anchor\" aria-label=\"Permalink: Z-Algorithm as string search algorithm\" href=\"#z-algorithm-as-string-search-algorithm\"\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\"\u003eThe Z-Algorithm discussed above leads to the simplest linear-time string matching algorithm. To obtain it, we have to simply concatenate the pattern \u003ccode\u003eP\u003c/code\u003e and text \u003ccode\u003eT\u003c/code\u003e in a string \u003ccode\u003eS = P$T\u003c/code\u003e where \u003ccode\u003e$\u003c/code\u003e is a character that does not appear neither in \u003ccode\u003eP\u003c/code\u003e nor \u003ccode\u003eT\u003c/code\u003e. Then we run the algorithm on \u003ccode\u003eS\u003c/code\u003e obtaining the Z-array. All we have to do now is scan the Z-array looking for elements equal to \u003ccode\u003en\u003c/code\u003e (which is the pattern length). When we find such value we can report an occurrence.\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(pattern: String) -\u0026gt; [Int]? {\n let patternLength: Int = pattern.count\n /* Let's calculate the Z-Algorithm on the concatenation of pattern and text */\n let zeta = ZetaAlgorithm(ptrn: pattern + \u0026quot;💲\u0026quot; + self)\n\n guard zeta != nil else {\n return nil\n }\n\n var indexe
7041
s: [Int] = [Int]()\n\n /* Scan the zeta array to find matched patterns */\n for i in 0 ..\u0026lt; zeta!.count {\n if zeta![i] == patternLength {\n indexes.append(i - patternLength - 1)\n }\n }\n\n guard !indexes.isEmpty else {\n return nil\n }\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\u003epattern\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 \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 /* Let's calculate the Z-Algorithm on the concatenation of pattern and text */\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\u003eptrn\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e pattern \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 \u003cspan class=\"pl-c1\"\u003e+\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eself\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n\n \u003cspan class=\"pl-k\"\u003eguard\u003c/span\u003e zeta \u003cspan class=\"pl-c1\"\u003e!=\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003enil\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\"\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 /* Scan the zeta array to find matched patterns */\n \u003cspan class=\"pl-k\"\u003efor\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ei\u003c/span\u003e \u003cspan class=\"pl-k\"\u003ein\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e..\u0026lt;\u003c/span\u003e zeta!\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003ecount \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e zeta!\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ei\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \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\u003ei \u003cspan class=\"pl-c1\"\u003e-\u003c/span\u003e patternLength \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\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. Let \u003ccode\u003eP = “CATA“\u003c/code\u003e and \u003ccode\u003eT = \"GAGAACATACATGACCAT\"\u003c/code\u003e be the pattern and the text. Let's concatenate them with the character \u003ccode\u003e$\u003c/code\u003e. We have the string \u003ccode\u003eS = \"CATA$GAGAACATACATGACCAT\"\u003c/code\u003e. After computing the Z-Algorithm on \u003ccode\u003eS\u003c/code\u003e we obtain:\u003c/p\u003e\n\u003cdiv class=\"snippet-clipboard-content notranslate position-relative overflow-auto\" data-snippet-clipboard-copy-content=\" 1 2\n 01234567890123456789012\n CATA$GAGAACATACATGACCAT\nZ 00000000004000300001300\n ^\"\u003e\u003cpre class=\"notranslate\"\u003e\u003ccode\u003e 1 2\n 01234567890123456789012\n CATA$GAGAACATACATGACCAT\nZ 00000000004000300001300\n ^\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eWe scan the Z-array and at position \u003ccode\u003e10\u003c/code\u003e we find \u003ccode\u003eZ[10] = 4 = n\u003c/code\u003e. So we can report a match occuring at text position \u003ccode\u003e10 - n - 1 = 5\u003c/code\u003e.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eAs said before, the complexity of this algorithm is linear. Defining \u003ccode\u003en\u003c/code\u003e and \u003ccode\u003em\u003c/code\u003e as pattern and text lengths, the final complexity we obtain is \u003ccode\u003eO(n + m + 1) = O(n + m)\u003c/code\u003e.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eCredits: This code is based 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":"Z-Algorithm String Search","anchor":"z-algorithm-string-search","htmlText":"Z-Algorithm String Search"},{"level":3,"text":"Z-Algorithm as pattern pre-processor","anchor":"z-algorithm-as-pattern-pre-processor","htmlText":"Z-Algorithm as pattern pre-processor"},{"level":3,"text":"Z-Algorithm as string search algorithm","anchor":"z-algorithm-as-string-search-algorithm","htmlText":"Z-Algorithm as string search algorithm"}],"siteNavLoginPath":"/login?return_to=https%3A%2F%2Fgithub.com%2Frreballos%2Fswift-algorithm-club%2Ftree%2Fmaster%2FZ-Algorithm"}},"totalCount":4,"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":"Closest Pair","path":"Closest Pair","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":"Genetic","path":"Genetic","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":"Introsort","path":"Introsort","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":"Myers Difference Algorithm","path":"Myers Difference Algorithm","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":"Points Lines Planes","path":"Points Lines Planes","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":"Simulated annealing","path":"Simulated annealing","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":"Sparse Table","path":"Sparse Table","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":".gitignore","path":".gitignore","contentType":"file"},{"name":".swiftlint.yml","path":".swiftlint.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":118}},"fileTreeProcessingTime":5.586135,"foldersToFetch":[],"treeExpanded":true,"symbolsExpanded":false,"csrf_tokens":{"/rreballos/swift-algorithm-club/branches":{"post":"CacQfsHazgR3Oc-IR5LW88VF3AUVuv7ulK7lpc01Z_qxFW7YHyiKQHJIR7CUomIepkwiWzdEgQ-3K-9zCMBXYg"},"/rreballos/swift-algorithm-club/branches/fetch_and_merge/master":{"post":"sw6B6rZAJtnMSwS735t6mGdQKA17RxkPkalt3W7_XEg87SzMHdbRjGTwJzXzK2mOK6ZQX6rcCObNt4jLGDbrpw"},"/rreballos/swift-algorithm-club/branches/fetch_and_merge/master?discard_changes=true":{"post":"LVgzZaEnkZD5VZ6qzK3cDeGetT3ECfd2FwvQB3-Hr6Ciu55DCrFmxVHuvSTgHc8brWjNbxWS5p9LFTURCU4YTw"}}},"title":"swift-algorithm-club/Z-Algorithm at master · rreballos/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}}}