prompt: You will be provided with a partial code base and an issue statement explaining a problem to resolve.
  <issue>
  Returning index instead of boolean when knuth_morris_pratt matches.
  In [knuth morris pratt algorithm](https://github.com/TheAlgorithms/Python/blob/master/strings/knuth_morris_pratt.py), I think it's better to return the "index" of the matched substring in case of success, and `-1` in case of failure, so that it would be consistent with the `str.find()` in Python. `True` and `False` aren't that helpful.
  
  </issue>
  <code>
  [start of strings/knuth_morris_pratt.py]
  1 from __future__ import annotations
  2 
  3 
  4 def kmp(pattern: str, text: str) -> bool:
  5     """
  6     The Knuth-Morris-Pratt Algorithm for finding a pattern within a piece of text
  7     with complexity O(n + m)
  8 
  9     1) Preprocess pattern to identify any suffixes that are identical to prefixes
  10 
  11         This tells us where to continue from if we get a mismatch between a character
  12         in our pattern and the text.
  13 
  14     2) Step through the text one character at a time and compare it to a character in
  15         the pattern updating our location within the pattern if necessary
  16 
  17     """
  18 
  19     # 1) Construct the failure array
  20     failure = get_failure_array(pattern)
  21 
  22     # 2) Step through text searching for pattern
  23     i, j = 0, 0  # index into text, pattern
  24     while i < len(text):
  25         if pattern[j] == text[i]:
  26             if j == (len(pattern) - 1):
  27                 return True
  28             j += 1
  29 
  30         # if this is a prefix in our pattern
  31         # just go back far enough to continue
  32         elif j > 0:
  33             j = failure[j - 1]
  34             continue
  35         i += 1
  36     return False
  37 
  38 
  39 def get_failure_array(pattern: str) -> list[int]:
  40     """
  41     Calculates the new index we should go to if we fail a comparison
  42     :param pattern:
  43     :return:
  44     """
  45     failure = [0]
  46     i = 0
  47     j = 1
  48     while j < len(pattern):
  49         if pattern[i] == pattern[j]:
  50             i += 1
  51         elif i > 0:
  52             i = failure[i - 1]
  53             continue
  54         j += 1
  55         failure.append(i)
  56     return failure
  57 
  58 
  59 if __name__ == "__main__":
  60     # Test 1)
  61     pattern = "abc1abc12"
  62     text1 = "alskfjaldsabc1abc1abc12k23adsfabcabc"
  63     text2 = "alskfjaldsk23adsfabcabc"
  64     assert kmp(pattern, text1) and not kmp(pattern, text2)
  65 
  66     # Test 2)
  67     pattern = "ABABX"
  68     text = "ABABZABABYABABX"
  69     assert kmp(pattern, text)
  70 
  71     # Test 3)
  72     pattern = "AAAB"
  73     text = "ABAAAAAB"
  74     assert kmp(pattern, text)
  75 
  76     # Test 4)
  77     pattern = "abcdabcy"
  78     text = "abcxabcdabxabcdabcdabcy"
  79     assert kmp(pattern, text)
  80 
  81     # Test 5)
  82     pattern = "aabaabaaa"
  83     assert get_failure_array(pattern) == [0, 1, 0, 1, 2, 3, 4, 5, 2]
  84
  [end of strings/knuth_morris_pratt.py]
  </code>
  
  I need you to solve this issue by generating a single patch file that I can apply directly to this repository using git apply. Please respond with a single patch file in the following format.
  <patch>
  diff --git a/file.py b/file.py
  --- a/file.py
  +++ b/file.py
  @@ -1,27 +1,35 @@
   def euclidean(a, b):
  -    while b:
  -        a, b = b, a % b
  -    return a
  +    if b == 0:
  +        return a
  +    return euclidean(b, a % b)
   
   
   def bresenham(x0, y0, x1, y1):
       points = []
       dx = abs(x1 - x0)
       dy = abs(y1 - y0)
  -    sx = 1 if x0 < x1 else -1
  -    sy = 1 if y0 < y1 else -1
  -    err = dx - dy
  +    x, y = x0, y0
  +    sx = -1 if x0 > x1 else 1
  +    sy = -1 if y0 > y1 else 1
   
  -    while True:
  -        points.append((x0, y0))
  -        if x0 == x1 and y0 == y1:
  -            break
  -        e2 = 2 * err
  -        if e2 > -dy:
  -            err -= dy
  -            x0 += sx
  -        if e2 < dx:
  -            err += dx
  -            y0 += sy
  +    if dx > dy:
  +        err = dx / 2.0
  +        while x != x1:
  +            points.append((x, y))
  +            err -= dy
  +            if err < 0:
  +                y += sy
  +                err += dx
  +            x += sx
  +    else:
  +        err = dy / 2.0
  +        while y != y1:
  +            points.append((x, y))
  +            err -= dx
  +            if err < 0:
  +                x += sx
  +                err += dy
  +            y += sy
  +
  +    points.append((x, y))
       return points
  
  </patch>
golden_diff: diff --git a/strings/knuth_morris_pratt.py b/strings/knuth_morris_pratt.py
  --- a/strings/knuth_morris_pratt.py
  +++ b/strings/knuth_morris_pratt.py
  @@ -1,7 +1,7 @@
   from __future__ import annotations
   
   
  -def kmp(pattern: str, text: str) -> bool:
  +def knuth_morris_pratt(text: str, pattern: str) -> int:
       """
       The Knuth-Morris-Pratt Algorithm for finding a pattern within a piece of text
       with complexity O(n + m)
  @@ -14,6 +14,12 @@
       2) Step through the text one character at a time and compare it to a character in
           the pattern updating our location within the pattern if necessary
   
  +    >>> kmp = "knuth_morris_pratt"
  +    >>> all(
  +    ...    knuth_morris_pratt(kmp, s) == kmp.find(s)
  +    ...    for s in ("kn", "h_m", "rr", "tt", "not there")
  +    ... )
  +    True
       """
   
       # 1) Construct the failure array
  @@ -24,7 +30,7 @@
       while i < len(text):
           if pattern[j] == text[i]:
               if j == (len(pattern) - 1):
  -                return True
  +                return i - j
               j += 1
   
           # if this is a prefix in our pattern
  @@ -33,7 +39,7 @@
               j = failure[j - 1]
               continue
           i += 1
  -    return False
  +    return -1
   
   
   def get_failure_array(pattern: str) -> list[int]:
  @@ -57,27 +63,38 @@
   
   
   if __name__ == "__main__":
  +    import doctest
  +
  +    doctest.testmod()
  +
       # Test 1)
       pattern = "abc1abc12"
       text1 = "alskfjaldsabc1abc1abc12k23adsfabcabc"
       text2 = "alskfjaldsk23adsfabcabc"
  -    assert kmp(pattern, text1) and not kmp(pattern, text2)
  +    assert knuth_morris_pratt(text1, pattern) and knuth_morris_pratt(text2, pattern)
   
       # Test 2)
       pattern = "ABABX"
       text = "ABABZABABYABABX"
  -    assert kmp(pattern, text)
  +    assert knuth_morris_pratt(text, pattern)
   
       # Test 3)
       pattern = "AAAB"
       text = "ABAAAAAB"
  -    assert kmp(pattern, text)
  +    assert knuth_morris_pratt(text, pattern)
   
       # Test 4)
       pattern = "abcdabcy"
       text = "abcxabcdabxabcdabcdabcy"
  -    assert kmp(pattern, text)
  +    assert knuth_morris_pratt(text, pattern)
  +
  +    # Test 5) -> Doctests
  +    kmp = "knuth_morris_pratt"
  +    assert all(
  +        knuth_morris_pratt(kmp, s) == kmp.find(s)
  +        for s in ("kn", "h_m", "rr", "tt", "not there")
  +    )
   
  -    # Test 5)
  +    # Test 6)
       pattern = "aabaabaaa"
       assert get_failure_array(pattern) == [0, 1, 0, 1, 2, 3, 4, 5, 2]
  
verification_info: {"golden_diff": "diff --git a/strings/knuth_morris_pratt.py b/strings/knuth_morris_pratt.py\n--- a/strings/knuth_morris_pratt.py\n+++ b/strings/knuth_morris_pratt.py\n@@ -1,7 +1,7 @@\n from __future__ import annotations\n \n \n-def kmp(pattern: str, text: str) -> bool:\n+def knuth_morris_pratt(text: str, pattern: str) -> int:\n     \"\"\"\n     The Knuth-Morris-Pratt Algorithm for finding a pattern within a piece of text\n     with complexity O(n + m)\n@@ -14,6 +14,12 @@\n     2) Step through the text one character at a time and compare it to a character in\n         the pattern updating our location within the pattern if necessary\n \n+    >>> kmp = \"knuth_morris_pratt\"\n+    >>> all(\n+    ...    knuth_morris_pratt(kmp, s) == kmp.find(s)\n+    ...    for s in (\"kn\", \"h_m\", \"rr\", \"tt\", \"not there\")\n+    ... )\n+    True\n     \"\"\"\n \n     # 1) Construct the failure array\n@@ -24,7 +30,7 @@\n     while i < len(text):\n         if pattern[j] == text[i]:\n             if j == (len(pattern) - 1):\n-                return True\n+                return i - j\n             j += 1\n \n         # if this is a prefix in our pattern\n@@ -33,7 +39,7 @@\n             j = failure[j - 1]\n             continue\n         i += 1\n-    return False\n+    return -1\n \n \n def get_failure_array(pattern: str) -> list[int]:\n@@ -57,27 +63,38 @@\n \n \n if __name__ == \"__main__\":\n+    import doctest\n+\n+    doctest.testmod()\n+\n     # Test 1)\n     pattern = \"abc1abc12\"\n     text1 = \"alskfjaldsabc1abc1abc12k23adsfabcabc\"\n     text2 = \"alskfjaldsk23adsfabcabc\"\n-    assert kmp(pattern, text1) and not kmp(pattern, text2)\n+    assert knuth_morris_pratt(text1, pattern) and knuth_morris_pratt(text2, pattern)\n \n     # Test 2)\n     pattern = \"ABABX\"\n     text = \"ABABZABABYABABX\"\n-    assert kmp(pattern, text)\n+    assert knuth_morris_pratt(text, pattern)\n \n     # Test 3)\n     pattern = \"AAAB\"\n     text = \"ABAAAAAB\"\n-    assert kmp(pattern, text)\n+    assert knuth_morris_pratt(text, pattern)\n \n     # Test 4)\n     pattern = \"abcdabcy\"\n     text = \"abcxabcdabxabcdabcdabcy\"\n-    assert kmp(pattern, text)\n+    assert knuth_morris_pratt(text, pattern)\n+\n+    # Test 5) -> Doctests\n+    kmp = \"knuth_morris_pratt\"\n+    assert all(\n+        knuth_morris_pratt(kmp, s) == kmp.find(s)\n+        for s in (\"kn\", \"h_m\", \"rr\", \"tt\", \"not there\")\n+    )\n \n-    # Test 5)\n+    # Test 6)\n     pattern = \"aabaabaaa\"\n     assert get_failure_array(pattern) == [0, 1, 0, 1, 2, 3, 4, 5, 2]\n", "issue": "Returning index instead of boolean when knuth_morris_pratt matches.\nIn [knuth morris pratt algorithm](https://github.com/TheAlgorithms/Python/blob/master/strings/knuth_morris_pratt.py), I think it's better to return the \"index\" of the matched substring in case of success, and `-1` in case of failure, so that it would be consistent with the `str.find()` in Python. `True` and `False` aren't that helpful.\n", "before_files": [{"content": "from __future__ import annotations\n\n\ndef kmp(pattern: str, text: str) -> bool:\n    \"\"\"\n    The Knuth-Morris-Pratt Algorithm for finding a pattern within a piece of text\n    with complexity O(n + m)\n\n    1) Preprocess pattern to identify any suffixes that are identical to prefixes\n\n        This tells us where to continue from if we get a mismatch between a character\n        in our pattern and the text.\n\n    2) Step through the text one character at a time and compare it to a character in\n        the pattern updating our location within the pattern if necessary\n\n    \"\"\"\n\n    # 1) Construct the failure array\n    failure = get_failure_array(pattern)\n\n    # 2) Step through text searching for pattern\n    i, j = 0, 0  # index into text, pattern\n    while i < len(text):\n        if pattern[j] == text[i]:\n            if j == (len(pattern) - 1):\n                return True\n            j += 1\n\n        # if this is a prefix in our pattern\n        # just go back far enough to continue\n        elif j > 0:\n            j = failure[j - 1]\n            continue\n        i += 1\n    return False\n\n\ndef get_failure_array(pattern: str) -> list[int]:\n    \"\"\"\n    Calculates the new index we should go to if we fail a comparison\n    :param pattern:\n    :return:\n    \"\"\"\n    failure = [0]\n    i = 0\n    j = 1\n    while j < len(pattern):\n        if pattern[i] == pattern[j]:\n            i += 1\n        elif i > 0:\n            i = failure[i - 1]\n            continue\n        j += 1\n        failure.append(i)\n    return failure\n\n\nif __name__ == \"__main__\":\n    # Test 1)\n    pattern = \"abc1abc12\"\n    text1 = \"alskfjaldsabc1abc1abc12k23adsfabcabc\"\n    text2 = \"alskfjaldsk23adsfabcabc\"\n    assert kmp(pattern, text1) and not kmp(pattern, text2)\n\n    # Test 2)\n    pattern = \"ABABX\"\n    text = \"ABABZABABYABABX\"\n    assert kmp(pattern, text)\n\n    # Test 3)\n    pattern = \"AAAB\"\n    text = \"ABAAAAAB\"\n    assert kmp(pattern, text)\n\n    # Test 4)\n    pattern = \"abcdabcy\"\n    text = \"abcxabcdabxabcdabcdabcy\"\n    assert kmp(pattern, text)\n\n    # Test 5)\n    pattern = \"aabaabaaa\"\n    assert get_failure_array(pattern) == [0, 1, 0, 1, 2, 3, 4, 5, 2]\n", "path": "strings/knuth_morris_pratt.py"}]}