Knuth-Morris-Pratt string search

Knuth-Morris-Pratt string search is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

< About Knuth-Morris-Pratt String Search Algorithm >

11l

Translation of: Python

F kmp_table(String word) -> [Int]
   V position = 1
   V candidate = 0

   V table = [0] * (word.len + 1)
   table[0] = -1

   L position < word.len
      I word[position] == word[candidate]
         table[position] = table[candidate]
      E
         table[position] = candidate
         L candidate >= 0 & word[position] != word[candidate]
            candidate = table[candidate]
      position++
      candidate++

   table[position] = candidate
   R table

F kmp_search(String text, word)
   V text_position = 0
   V word_position = 0

   [Int] positions
   V number_of_positions = 0
   V table = kmp_table(word)

   L text_position < text.len
      I word[word_position] == text[text_position]
         text_position++
         word_position++
         I word_position == word.len
            positions.append(text_position - word_position)
            number_of_positions++
            word_position = table[word_position]
      E
         word_position = table[word_position]
         I word_position < 0
            text_position++
            word_position++

   R (positions, number_of_positions)

V TEST_CASES = [(‘GCTAGCTCTACGAGTCTA’, ‘TCTA’),
                (‘GGCTATAATGCGTA’, ‘TAATAAA’),
                (‘there would have been a time for such a word’, ‘word’),
                (‘needle need noodle needle’, ‘needle’),
                (‘InhisbookseriesTheArtofComputerProgrammingpublishedbyAddisonWesley’""
                 ‘DKnuthusesanimaginarycomputertheMIXanditsassociatedmachinecodeand’""
                 ‘assemblylanguagestoillustratetheconceptsandalgorithmsastheyare’""
                 ‘presented’, ‘put’),
                (‘InhisbookseriesTheArtofComputerProgrammingpublishedbyAddisonWesley’""
                 ‘DKnuthusesanimaginarycomputertheMIXanditsassociatedmachinecodeand’""
                 ‘assemblylanguagestoillustratetheconceptsandalgorithmsastheyare’""
                 ‘presented’, ‘and’),
                (‘Nearby farms grew a half acre of alfalfa on the dairy's behalf, ’""
                 ‘with bales of all that alfalfa exchanged for milk.’, ‘alfalfa’)]

L(text, word) TEST_CASES
   V (positions, number_of_positions) = kmp_search(text, word)

   I number_of_positions == 0
      print(‘`’word‘` not found in `’text[0.<10]‘...`’)
   E I number_of_positions == 1
      print(‘Found `’word‘` in `’text[0.<10]‘...` once at ’positions‘.’)
   E
      print(‘Found `’word‘` in `’text[0.<10]‘...` ’number_of_positions‘ times at ’positions‘.’)

Output:

Found `TCTA` in `GCTAGCTCTA...` 2 times at [6, 14].
`TAATAAA` not found in `GGCTATAATG...`
Found `word` in `there woul...` once at [40].
Found `needle` in `needle nee...` 2 times at [0, 19].
Found `put` in `Inhisbooks...` 2 times at [26, 90].
Found `and` in `Inhisbooks...` 3 times at [101, 128, 171].
Found `alfalfa` in `Nearby far...` 2 times at [33, 87].

Emacs Lisp

(defun kmp_compile_pattern (pattern)
  "Compile pattern to DFA."

  (defun create-2d-array (x y init)
    (let ((arr1 (make-vector x nil)))
      (dotimes (i x)
	(aset arr1 i (make-vector y init)) )
      arr1 ) )
  
  (let* ((patLen (length pattern))
	 (R 256)
         (restartPos 0)
	 (dfa (create-2d-array R patLen 0)))
    
    (aset (aref dfa (elt pattern 0)) 0 1)

    (let ((patPos 0))
      (while (progn (setq patPos (1+ patPos)) (< patPos patLen))
	(dotimes (c R)
	  (aset (aref dfa c) patPos (aref (aref dfa c) restartPos)) )
	
	(aset (aref dfa (elt pattern patPos)) patPos (1+ patPos))
	(setq restartPos
	      (aref (aref dfa (elt pattern patPos)) restartPos) )
	)
      )
    dfa )
  )

(defun kmp_search (pattern text)
  "Pattern search with KMP algorithm."
  (let ((dfa (kmp_compile_pattern pattern)))

    (let ((textPos 0) (patPos 0) (N (length text)) (M (length pattern)))
      (while (and (< textPos N) (< patPos M))
	(setq patPos (aref (aref dfa (elt text textPos)) patPos))
	(setq textPos (1+ textPos)) )
      
      (if (= patPos M) (- textPos M) N ) ) ) )

Fortran

      module kmp_mod
      use iso_fortran_env
      implicit none
      private
      public :: kmpsearch
      contains
        !This subroutine creates the "fail" table used for the KMP algorithm
      pure subroutine createtable(pattern,patlen,table)
 
      implicit none
!
! Dummy arguments
!
      integer :: patlen
      character(*) :: pattern
      integer , dimension(:) :: table
      intent (in) patlen , pattern
      intent (inout) table
!
! Local variables
!
      integer :: counter
      integer :: i
      integer :: j
!*Code                                                                  
      counter=2
      i=1
      j=0
            !Determine the table/fail value for each letter in the pattern
      do i=1 , patlen
         j=i
         do
            ! If j is equal to zero, then there is no offset/fail value required. Therefore, just set the fail value to 0
            if( j==1 )then
               table(counter)=1
               counter=counter+1
               exit
            end if
 
            ! If a match is made, the fail value can be imcremented by one (based off the fail value of the previous character in the pattern)
            if( pattern(table(j):table(j))==pattern(i:i) )then
               table(counter)=table(j)+1
               counter=counter+1
               exit
            end if
 
            ! If neither if statement is true, restart the fail value counter
            j=table(j)
         end do
      end do
      end subroutine createtable
 
      ! This subroutine executes the string search using the KMP algorithm (fail table)
      pure function kmpsearch(pattern,patlen,line,linelen)              &
                            & result(foundmatch)
 
      implicit none
!
! Dummy arguments
!
      character(*) :: line
      integer :: linelen
      integer :: patlen
      character(*) :: pattern
      intent (in) line , linelen , patlen , pattern
!
! Local variables
!
      integer :: foundmatch
      integer :: indice
      integer :: match
      integer , dimension(256) :: table
!*Code                                                                  
      if( (patlen==0) .or. (linelen==0) .or. (linelen<patlen) )then
         foundmatch=-1
         return
      end if
 
      indice=1
      match=0
      foundmatch=-1
      call createtable(pattern,patlen,table)
            !Search the entire string
      do while ( indice+match<=linelen )
         if( match+1<patlen+1 )then
 
            ! If the character matches the character we are expecting (based on where in the pattern we have already matched characters with) increment the match indice
            if( line(indice+match:indice+match)==pattern(match+1:match+1) )then
               match=match+1
 
               ! If the match indice is equal to the length of the pattern, that means we have matched the entire pattern
               if( match==patlen )then
                  foundmatch=indice            !-1
                  exit !Found
               end if
                    !Look at the table to determine what indice to check next
            ! If no match was made on the first letter of the pattern, then just increment the indice counter by one and check again
            else if( match==0 )then
               indice=indice+1
            ! Check how many characters to skip ahead (the point of the KMP algorithm)
            else
               indice=indice+match+1-table(match+1)
               match=table(match+1)-1
            end if
         ! If no match was made after scanning the length of the pattern, need increment the indice counter and check again
         else if( match==0 )then
            indice=indice+1                !Not even a partial match, try next character
         else             !Check how many characters to skip ahead (the point of the KMP algorithm)
            indice=indice+match+1-table(match+1)
            match=table(match+1)-1
         end if
      end do 
!       'No match found'
      return
      end function kmpsearch
      end module kmp_mod

FreeBASIC

Adapted from Wren

Dim Shared As Integer t()
Dim Shared As Integer indices()

Sub Tabla(patron As String)
    Dim As Integer nc = Len(patron)
    Redim As Integer t(nc)
    Dim As Integer idx = 1  ' index into table
    Dim As Integer lon = 0  ' length of previous longest prefix

    While idx < nc
        If patron[idx] = patron[lon] Then
            lon += 1
            t(idx) = lon
            idx += 1
        Elseif lon <> 0 Then
            lon = t(lon-1)
        Else
            t(idx) = 0
            idx += 1
        End If
    Wend
End Sub

Sub BusquedaKMP(texto As String, patron As String)
    Dim As Integer hc = Len(texto)
    Dim As Integer nc = Len(patron)
    Dim As Integer i = 0   ' index into haystack
    Dim As Integer j = 0   ' index into needle
    Dim As Integer cont = 1
    
    Tabla(patron)
    
    While i < hc
        If patron[j] = texto[i] Then
            i += 1
            j += 1
        End If
        If j = nc Then
            Redim Preserve indices(cont)
            indices(cont) = (i - j)
            cont += 1
            j = t(j-1)
        Elseif i < hc And patron[j] <> texto[i] Then
            If j <> 0 Then j = t(j-1) Else i += 1
        End If
    Wend
End Sub

Dim As Integer i, j, k
Dim As String cadenas(1 To 6) = {"GCTAGCTCTACGAGTCTA", "GGCTATAATGCGTA", _
"there would have been a time for such a word", "needle need noodle needle", _
"InhisbookseriesTheArtofComputerProgrammingpublishedbyAddisonWesleyDKnuthusesanimaginarycomputertheMIXanditsassociatedmachinecodeandassemblylanguagestoillustratetheconceptsandalgorithmsastheyarepresented", _
"Nearby farms grew a half acre of alfalfa on the dairy's behalf, with bales of all that alfalfa exchanged for milk."}
Dim As String palabra(1 To 7) = { _
"TCTA", "TAATAAA", "word", "needle", "put", "and", "alfalfa"}

For i = 1 To Ubound(cadenas)
    Print Using "text# = &"; i; cadenas(i)
Next
Print
For i = 1 To Ubound(palabra)
    j = Iif(i < 6, i, i-1)
    Print Using "Found '&' in 'text#' at indices [ "; palabra(i); j;
    BusquedaKMP(cadenas(j), palabra(i))
    If Ubound(indices) > 0 Then
        For k = 1 To Ubound(indices)
            Print indices(k) & ", ";
        Next
    Else
        Print " ";
    End If
    Print Chr(8) & Chr(8) & " ]"
    Erase indices
Next

Sleep

Output:

text1 = GCTAGCTCTACGAGTCTA
text2 = GGCTATAATGCGTA
text3 = there would have been a time for such a word
text4 = needle need noodle needle
text5 = InhisbookseriesTheArtofComputerProgrammingpublishedbyAddisonWesleyDKnuthusesanimaginarycomputertheMIXanditsassociatedmachinecodeandassemblylanguagestoillustratetheconceptsandalgorithmsastheyarepresented
text6 = Nearby farms grew a half acre of alfalfa on the dairy's behalf, with bales of all that alfalfa exchanged for milk.

Found 'TCTA' in 'text1' at indices [ 6, 14 ]
Found 'TAATAAA' in 'text2' at indices [ ]
Found 'word' in 'text3' at indices [ 40 ]
Found 'needle' in 'text4' at indices [ 0, 19 ]
Found 'put' in 'text5' at indices [ 26, 90 ]
Found 'and' in 'text5' at indices [ 101, 128, 171 ]
Found 'alfalfa' in 'text6' at indices [ 33, 87 ]

J

Implementation:

kmp_table=: {{
  j=. 0
  T=. _1
  for_ch. }.y do.
    if. ch=j{y do.
      T=. T,j{T
    else.
      T=. T,j while. (0<:j) * ch~:j{y do. j=. j{T end.
    end.
    j=. j+1
  end.
  T=. T, j
}}

kmp_search=: {{
  b=. 0#~#y
  k=. _1
  f=. _1+#x
  T=. kmp_table x
  for_ch. y do.
    if. ch=x{~k=.k+1 do.
      if. f=k do.
        b=. 1 (ch_index-k)} b
        k=. k{T
      end.
    else.
      whilst. _1<k do.
        if. ch=x{~k=. k{T do. break. end.
      end.
    end.
  end.
  I. b
}}

Task examples:

   text1=: 'InhisbookseriesTheArtofComputerProgrammingpublishedbyAddisonWesleyDKnuthusesanimaginarycomputertheMIXanditsassociatedmachinecodeandassemblylanguagestoillustratetheconceptsandalgorithmsastheyarepresented'
   text2=: 'Nearby farms grew a half acre of alfalfa on the dairy''s behalf, with bales of all that alfalfa exchanged for milk.'
   'put' kmp_search text1
26 90
   'and' kmp_search text1
101 128 171
   'and' kmp_search text2

   'alfalfa' kmp_search text2
33 87

(J uses index 0 for the first character in a sequence of characters.)

jq

Adapted from Wren

Works with: jq

The program will also work with gojq once the prefix "KMP::" is omitted in the two lines in which it occurs.

# search for the string needle in the string haystack
def KMP::search(haystack; needle):

  def table_($needle):
    ($needle|length) as $nc
    | {t: [range(0; $nc) | 0],
       i: 1,   # index into table
       len: 0  # length of previous longest prefix
      }
    | until(.i >= .nc;
            if $needle[.i] == $needle[.len]
	    then .len += 1
            | .t[.i] = .len
            | .i += 1
            elif .len != 0
            then .len = .t[.len-1]
            else .t[.i] = 0
            | .i += 1
	    end )
    | .t ;
  
  { haystack: (haystack|explode),
    needle: (needle|explode),
    hc: (haystack|length),
    nc: (needle|length),
    indices: [],
    i: 0,        # index into haystack
    j: 0         # index into needle
  }
  | table_(.needle) as $t
  | until (.i >= .hc;
           if .needle[.j] == .haystack[.i]
           then .i += 1
           | .j += 1
           else .
           end
           | if .j == .nc
             then .indices = .indices + [.i - .j]
             | .j = $t[.j-1]
             elif (.i < .hc and .needle[.j] != .haystack[.i])
             then if .j != 0 then .j = $t[.j-1] else .i += 1 end
             else .
             end )
  | .indices ;


# Examples
def texts: [ 
    "GCTAGCTCTACGAGTCTA",
    "GGCTATAATGCGTA",
    "there would have been a time for such a word",
    "needle need noodle needle",
    "InhisbookseriesTheArtofComputerProgrammingpublishedbyAddisonWesleyDKnuthusesanimaginarycomputertheMIXanditsassociatedmachinecodeandassemblylanguagestoillustratetheconceptsandalgorithmsastheyarepresented",
    "Nearby farms grew a half acre of alfalfa on the dairy's behalf, with bales of all that alfalfa exchanged for milk."
];

def pats: ["TCTA", "TAATAAA", "word", "needle", "put", "and", "alfalfa"];


def tasks($texts; $pats):
  range (0; $texts|length) | "text\(.+1) = \($texts[.])",
"",
  (range (0; $pats|length) as $i
   | (if $i < 5 then $i else $i-1 end) as $j
   | "Found '\($pats[$i])' in text\($j+1) at indices \(KMP::search($texts[$j]; $pats[$i]) )" ) ;

tasks(texts; pats)

Invocation: jq -nr -f kmp-string-search.jq

Output:

text1 = GCTAGCTCTACGAGTCTA
text2 = GGCTATAATGCGTA
text3 = there would have been a time for such a word
text4 = needle need noodle needle
text5 = InhisbookseriesTheArtofComputerProgrammingpublishedbyAddisonWesleyDKnuthusesanimaginarycomputertheMIXanditsassociatedmachinecodeandassemblylanguagestoillustratetheconceptsandalgorithmsastheyarepresented
text6 = Nearby farms grew a half acre of alfalfa on the dairy's behalf, with bales of all that alfalfa exchanged for milk.

Found 'TCTA' in text1 at indices [6, 14]
Found 'TAATAAA' in text2 at indices []
Found 'word' in text3 at indices [40]
Found 'needle' in text4 at indices [0, 19]
Found 'put' in text5 at indices [26, 90]
Found 'and' in text5 at indices [101, 128, 171]
Found 'alfalfa' in text6 at indices [33, 87]

Julia

"""
    function kmp_table(W)

input:
    an array of characters, W (the word to be analyzed)
output:
    an array of integers, T (the table to be filled)
define variables:
    an integer, i ← 2 (the current one-based position we are computing in T)
    an integer, j ← 0 (the additive to index i in W of the next character of the current candidate substring)
"""
function kmp_table(W)
    len = length(W)
    T = zeros(Int, len)
    # start with the second letter of W, looking for patterns in W
    i = 2
    while i < len
        j = 0
        while i + j <= len # avoid overshooting end with index
            # compute the longest proper prefix
            if W[i + j] == W[j + 1]
                T[i + j] = T[i + j - 1] + 1
            else
                T[i + j] = 0 # back to start
                j += 1
                break
            end
            j += 1
        end       
        # entry in T found, so begin at next starting point along W
        i += j
    end
    return T
end    

"""
    function kmp_search(S, W)
    
input:
    an array of characters, S (the text to be searched)
    an array of characters, W (the word sought)
output:
    an array of integers, P (positions in S at which W is found)

define variables (one based indexing in Julia differs from the Wikipedia example):
    an integer, i ← 1 (the position of the current character in S)
    an integer, j ← 1 (the position of the current character in W)
    an array of integers, T (the table, computed elsewhere)
"""
function kmp_search(S, W)
    lenW, lenS = length(W), length(S)    
    i, P = 1, Int[]      
    T = kmp_table(W) # get pattern table
    while i <= lenS - lenW + 1
        for j in 1:lenW
            if S[i + j - 1] != W[j]
                # pattern not found, so skip unnecessary inner loops
                i += T[j] + 1
                @goto next_outer_loop
            end
        end
        # found pattern W in S, so add to output P
        push!(P, i)
        i += 1
        @label next_outer_loop
    end                
    return P    
end

const text1 = "InhisbookseriesTheArtofComputerProgrammingpublishedbyAddisonWesleyDKnuthusesanimaginarycomputertheMIXanditsassociatedmachinecodeandassemblylanguagestoillustratetheconceptsandalgorithmsastheyarepresented" 
const text2 = "Nearby farms grew a half acre of alfalfa on the dairy's behalf, with bales of all that alfalfa exchanged for milk."
const pat1, pat2, pat3 = "put", "and", "alfalfa"
 
println("Found <$pat1> at: (one-based indices) ", kmp_search(text1, pat1))
println("Found <$pat2> at: (one-based indices) ", kmp_search(text1, pat2))
println("Found <$pat3> at: (one-based indices) ", kmp_search(text2, pat3))

Output:

Found <put> at: (one-based indices) [27, 91]
Found <and> at: (one-based indices) [102, 129, 172]
Found <alfalfa> at: (one-based indices) [34, 88]

Nim

This is a translation of pseudocode in Wikipedia page. We use the examples of Wren solution.

import std/[strformat, strutils]

func kmpTable(w: string): seq[int] =
  ## Build the partial match table for "w".
  result.setLen w.len + 1
  var pos = 1
  var cnd = 0
  result[0] = -1
  while pos < w.len:
    if w[pos] == w[cnd]:
      result[pos] = result[cnd]
    else:
      result[pos] = cnd
      while cnd >= 0 and w[pos] != w[cnd]:
        cnd = result[cnd]
    inc pos
    inc cnd
  result[pos] = cnd

func kmpSearch(s, w: string): seq[int] =
  ## Return the positions of "w" ins "s".
  var j, k = 0
  let t = kmpTable(w)
  while j < s.len:
    if w[k] == s[j]:
      inc j
      inc k
      if k == w.len:
        result.add j - k
        k = t[k]
    else:
      k = t[k]
      if k < 0:
        inc j
        inc k


const
  Texts = ["GCTAGCTCTACGAGTCTA",
           "GGCTATAATGCGTA",
           "there would have been a time for such a word",
           "needle need noodle needle",
           "InhisbookseriesTheArtofComputerProgrammingpublishedbyAddisonWesleyDKnuth" &
             "usesanimaginarycomputertheMIXanditsassociatedmachinecodeandassembly" &
             "languagestoillustratetheconceptsandalgorithmsastheyarepresented",
           "Nearby farms grew a half acre of alfalfa on the dairy's behalf, " &
             "with bales of all that alfalfa exchanged for milk."
          ]

  # Couples (pattern, index of text to use).
  Patterns = {"TCTA": 0, "TAATAAA": 1, "word": 2, "needle": 3, "put": 4, "and": 4, "alfalfa": 5}

for i, text in Texts:
  echo &"Text{i+1} = {text}"
echo()

for i, (pattern, j) in Patterns:
  let indices = Texts[j].kmpSearch(pattern)
  if indices.len > 0:
    echo &"Found “{pattern}” in “Text{j+1}” at indices {indices.join(\", \")}."
  else:
    echo &"Not found “{pattern}” in “Text{j+1}”."

Output:

Text1 = GCTAGCTCTACGAGTCTA
Text2 = GGCTATAATGCGTA
Text3 = there would have been a time for such a word
Text4 = needle need noodle needle
Text5 = InhisbookseriesTheArtofComputerProgrammingpublishedbyAddisonWesleyDKnuthusesanimaginarycomputertheMIXanditsassociatedmachinecodeandassemblylanguagestoillustratetheconceptsandalgorithmsastheyarepresented
Text6 = Nearby farms grew a half acre of alfalfa on the dairy's behalf, with bales of all that alfalfa exchanged for milk.

Found “TCTA” in “Text1” at indices 6, 14.
Not found “TAATAAA” in “Text2”.
Found “word” in “Text3” at indices 40.
Found “needle” in “Text4” at indices 0, 19.
Found “put” in “Text5” at indices 26, 90.
Found “and” in “Text5” at indices 101, 128, 171.
Found “alfalfa” in “Text6” at indices 33, 87.

Perl

Translation of: Raku

use v5.36;

sub kmp_search ($S, $W) {
    my @S = split '', $S;
    my @W = split '', $W;

   sub kmp_table (@W) {
        my($pos,$cnd,@T) = (1,0,-1);
        for (; $pos < @W ; $pos++, $cnd++) {
            if ($W[$pos] eq $W[$cnd]) {
                $T[$pos]  = $T[$cnd]
            } else {
                $T[$pos]  = $cnd;
                while ($cnd >= 0 and $W[$pos] ne $W[$cnd]) { $cnd = $T[$cnd] }
            }
        }
        $T[$pos] = $cnd;
        @T
    }

    my @I;
    my ($k,@T) = (0,kmp_table @W);
    for (my $j=0; $j < @S;) {
        if ($W[$k] eq $S[$j]) {
            $j++; $k++;
            if ($k == @W) {
                push @I,  $j - $k;
                $k = $T[$k]
            }
        } else {
            ($j++, $k++) if ($k = $T[$k]) < 0
        }
    }
    @I
}

my @texts = (
    "GCTAGCTCTACGAGTCTA",
    "GGCTATAATGCGTA",
    "there would have been a time for such a word",
    "needle need noodle needle",
    "InhisbookseriesTheArtofComputerProgrammingpublishedbyAddisonWesleyDKnuthusesanimaginarycomputertheMIXanditsassociatedmachinecodeandassemblylanguagestoillustratetheconceptsandalgorithmsastheyarepresented",
    "Nearby farms grew a half acre of alfalfa on the dairy's behalf, with bales of all that alfalfa exchanged for milk.",
);
my @pats = <TCTA TAATAAA word needle put and alfalfa>;

say "text$_ = $texts[$_]" for 0..$#texts;
say '';

for (0.. $#pats) {
    my $j = $_ < 5 ? $_ : $_-1 ; # for searching text4 twice
    say "Found '$pats[$_]' in 'text$j' at indices " . join ', ', kmp_search($texts[$j],$pats[$_]);
}

Output:

text0 = GCTAGCTCTACGAGTCTA
text1 = GGCTATAATGCGTA
text2 = there would have been a time for such a word
text3 = needle need noodle needle
text4 = InhisbookseriesTheArtofComputerProgrammingpublishedbyAddisonWesleyDKnuthusesanimaginarycomputertheMIXanditsassociatedmachinecodeandassemblylanguagestoillustratetheconceptsandalgorithmsastheyarepresented
text5 = Nearby farms grew a half acre of alfalfa on the dairy's behalf, with bales of all that alfalfa exchanged for milk.

Found 'TCTA' in 'text0' at indices 6, 14
Found 'TAATAAA' in 'text1' at indices
Found 'word' in 'text2' at indices 40
Found 'needle' in 'text3' at indices 0, 19
Found 'put' in 'text4' at indices 26, 90
Found 'and' in 'text4' at indices 101, 128, 171
Found 'alfalfa' in 'text5' at indices 33, 87

Phix

--
-- demo\rosetta\KnuthMorrisPratt.exw
-- =================================
--
-- based on https://www-igm.univ-mlv.fr/~lecroq/string/node8.html#SECTION0080
--
with javascript_semantics
function preKmp(string pat)
    integer m = length(pat), i = 1, j = 0
    sequence kmpNext = repeat(-1,m+1)
    pat &= '\0'
    while i <= m do
        while j > 0 and pat[i] != pat[j] do
            j = kmpNext[j]+1
        end while
        i += 1
        j += 1
        if pat[i] == pat[j] then
            kmpNext[i] = kmpNext[j]
        else
            kmpNext[i] = j-1
        end if
    end while
    return kmpNext
end function

procedure KMP(string pat, s, bool case_insensitive = false)
    string pins = sprintf("`%s` in `%s`",{pat,shorten(s,"characters",10)})
    if case_insensitive then {pat,s} = lower({pat,s}) end if
    /* Preprocessing */
    sequence kmpNext = preKmp(pat)
    /* Searching */
    sequence res = {}
    integer i = 0, j = 0,
            n = length(s),
            m = length(pat),
            cc = 0
    while j < n do
        while i > -1 do
            cc += 1
            if pat[i+1] = s[j+1] then exit end if
            i = kmpNext[i+1]
        end while
        i += 1
        j += 1
        if i >= m then
            res &= j-i+1
            i = kmpNext[i+1]
        end if
    end while
    /* Output */
    string ccs = sprintf("(%d character comparisons)",cc)
    if length(res) then
        string many = ordinant(length(res))
        printf(1,"Found %s %s at %v %s\n",{pins,many,res,ccs})
    else
        printf(1,"No %s %s\n",{pins,ccs})
    end if
end procedure

KMP("GCAGAGAG","GCATCGCAGAGAGTATACAGTACG")
KMP("TCTA","GCTAGCTCTACGAGTCTA")
KMP("TAATAAA","GGCTATAATGCGTA")
KMP("word","there would have been a time for such a word")
KMP("needle","needle need noodle needle")
constant book = "InhisbookseriesTheArtofComputerProgrammingpublishedbyAddisonWesley"&
                "DKnuthusesanimaginarycomputertheMIXanditsassociatedmachinecodeand"&
                "assemblylanguagestoillustratetheconceptsandalgorithmsastheyarepresented"
KMP("put",book)
KMP("and",book)
constant farm = "Nearby farms grew a half acre of alfalfa on the dairy's behalf, with "&
                "bales of all that alfalfa exchanged for milk."
KMP("alfalfa",farm)
--KMP("aLfAlfa",farm)       -- none
--KMP("aLfAlfa",farm,true)  -- as -2

Output:

Significantly higher character comparison counts than Boyer-Moore_string_search#Phix.
Also higher than those on the above (lecroq) link, probably because this carries on for all matches.

Found `GCAGAGAG` in `GCATCGCAGAGAGTATACAGTACG` once at {6} (26 character comparisons)
Found `TCTA` in `GCTAGCTCTACGAGTCTA` twice at {7,15} (19 character comparisons)
No `TAATAAA` in `GGCTATAATGCGTA` (16 character comparisons)
Found `word` in `there woul...uch a word (44 characters)` once at {41} (45 character comparisons)
Found `needle` in `needle need noodle needle` twice at {1,20} (27 character comparisons)
Found `put` in `Inhisbooks...epresented (202 characters)` twice at {27,91} (205 character comparisons)
Found `and` in `Inhisbooks...epresented (202 characters)` three times at {102,129,172} (216 character comparisons)
Found `alfalfa` in `Nearby far... for milk. (114 characters)` twice at {34,88} (125 character comparisons)

Python

Based on pseudocode found in the Wikipedia article. Uses test cases from the #Wren solution.

"""Knuth-Morris-Pratt string search. Requires Python >= 3.7."""
from typing import List
from typing import Tuple


def kmp_search(text: str, word: str) -> Tuple[List[int], int]:
    text_position = 0
    word_position = 0

    positions: List[int] = []
    number_of_positions = 0
    table = kmp_table(word)

    while text_position < len(text):
        if word[word_position] == text[text_position]:
            text_position += 1
            word_position += 1
            if word_position == len(word):
                positions.append(text_position - word_position)
                number_of_positions += 1
                word_position = table[word_position]
        else:
            word_position = table[word_position]
            if word_position < 0:
                text_position += 1
                word_position += 1

    return positions, number_of_positions


def kmp_table(word: str) -> List[int]:
    position = 1
    candidate = 0

    table = [0] * (len(word) + 1)
    table[0] = -1

    while position < len(word):
        if word[position] == word[candidate]:
            table[position] = table[candidate]
        else:
            table[position] = candidate
            while candidate >= 0 and word[position] != word[candidate]:
                candidate = table[candidate]
        position += 1
        candidate += 1

    table[position] = candidate
    return table


TEST_CASES = [
    ("GCTAGCTCTACGAGTCTA", "TCTA"),
    ("GGCTATAATGCGTA", "TAATAAA"),
    ("there would have been a time for such a word", "word"),
    ("needle need noodle needle", "needle"),
    (
        (
            "InhisbookseriesTheArtofComputerProgrammingpublishedbyAddisonWesley"
            "DKnuthusesanimaginarycomputertheMIXanditsassociatedmachinecodeand"
            "assemblylanguagestoillustratetheconceptsandalgorithmsastheyare"
            "presented"
        ),
        "put",
    ),
    (
        (
            "InhisbookseriesTheArtofComputerProgrammingpublishedbyAddisonWesley"
            "DKnuthusesanimaginarycomputertheMIXanditsassociatedmachinecodeand"
            "assemblylanguagestoillustratetheconceptsandalgorithmsastheyare"
            "presented"
        ),
        "and",
    ),
    (
        (
            "Nearby farms grew a half acre of alfalfa on the dairy's behalf, "
            "with bales of all that alfalfa exchanged for milk."
        ),
        "alfalfa",
    ),
]


def main():
    for text, word in TEST_CASES:
        positions, number_of_positions = kmp_search(text, word)

        if number_of_positions == 0:
            print(f"`{word}` not found in `{text[:10]}...`")
        elif number_of_positions == 1:
            print(f"Found `{word}` in `{text[:10]}...` once at {positions}.")
        else:
            print(
                f"Found `{word}` in `{text[:10]}...` {number_of_positions} times at {positions}."
            )


if __name__ == "__main__":
    main()

Output:

Found `TCTA` in `GCTAGCTCTA...` 2 times at [6, 14].
`TAATAAA` not found in `GGCTATAATG...`
Found `word` in `there woul...` once at [40].
Found `needle` in `needle nee...` 2 times at [0, 19].
Found `put` in `Inhisbooks...` 2 times at [26, 90].
Found `and` in `Inhisbooks...` 3 times at [101, 128, 171].
Found `alfalfa` in `Nearby far...` 2 times at [33, 87].

Raku

Based on pseudocode found in WP (kmp_search & kmp_table). Data and output format mostly follows the Wren entry.

# 20220810 Raku programming solution

sub kmp_search (@S where *.Bool, @W where *.Bool) {

   sub kmp_table (@W where *.Bool) {
      loop (my ($pos,$cnd,@T) = 1,0,-1 ; $pos < @W.elems ; ($pos, $cnd)>>++) {
         if @W[$pos] eq @W[$cnd] {
            @T[$pos]  = @T[$cnd]
         } else {
            @T[$pos]  = $cnd;
            while $cnd ≥ 0 and @W[$pos] ne @W[$cnd] { $cnd = @T[$cnd] }
         }
      }
      @T[$pos] = $cnd;
      return @T
   }

   return gather loop (my ($j,$k,@T) = 0,0, |kmp_table @W; $j < @S.elems; ) { 
      if @W[$k] eq @S[$j] { 
         ($j, $k)>>++;   
         if $k == @W.elems { 
	    take $j - $k;
            $k = @T[$k]  
         } 
      } else {
         ($j, $k)>>++ if ($k = @T[$k]) < 0    
      }
   }
}

my @texts = [
   "GCTAGCTCTACGAGTCTA",
   "GGCTATAATGCGTA",
   "there would have been a time for such a word",
   "needle need noodle needle",
   "BharôtভাৰতBharôtভারতIndiaBhāratભારતBhāratभारतBhārataಭಾರತBhāratभारतBhāratamഭാരതംBhāratभारतBhāratभारतBharôtôଭାରତBhāratਭਾਰਤBhāratamभारतम्Bārataபாரதம்BhāratamഭാരതംBhāratadēsamభారతదేశం",
   "InhisbookseriesTheArtofComputerProgrammingpublishedbyAddisonWesleyDKnuthusesanimaginarycomputertheMIXanditsassociatedmachinecodeandassemblylanguagestoillustratetheconceptsandalgorithmsastheyarepresented",
   "Nearby farms grew a half acre of alfalfa on the dairy's behalf, with bales of all that alfalfa exchanged for milk.",
];

my @pats = ["TCTA", "TAATAAA", "word", "needle", "ഭാരതം", "put", "and", "alfalfa"];

say "text$_ = @texts[$_]" for @texts.keys ; 
say();

for @pats.keys {
   my \j = $_ < 6 ?? $_ !! $_-1 ; # for searching text5 twice
   say "Found '@pats[$_]' in 'text{j}' at indices ", kmp_search @texts[j].comb, @pats[$_].comb
}

Output:

text0 = GCTAGCTCTACGAGTCTA
text1 = GGCTATAATGCGTA
text2 = there would have been a time for such a word
text3 = needle need noodle needle
text4 = BharôtভাৰতBharôtভারতIndiaBhāratભારતBhāratभारतBhārataಭಾರತBhāratभारतBhāratamഭാരതംBhāratभारतBhāratभारतBharôtôଭାରତBhāratਭਾਰਤBhāratamभारतम्Bārataபாரதம்BhāratamഭാരതംBhāratadēsamభారతదేశం
text5 = InhisbookseriesTheArtofComputerProgrammingpublishedbyAddisonWesleyDKnuthusesanimaginarycomputertheMIXanditsassociatedmachinecodeandassemblylanguagestoillustratetheconceptsandalgorithmsastheyarepresented
text6 = Nearby farms grew a half acre of alfalfa on the dairy's behalf, with bales of all that alfalfa exchanged for milk.

Found 'TCTA' in 'text0' at indices (6 14)
Found 'TAATAAA' in 'text1' at indices ()
Found 'word' in 'text2' at indices (40)
Found 'needle' in 'text3' at indices (0 19)
Found 'ഭാരതം' in 'text4' at indices (68 138)
Found 'put' in 'text5' at indices (26 90)
Found 'and' in 'text5' at indices (101 128 171)
Found 'alfalfa' in 'text6' at indices (33 87)

Sidef

Translation of: Raku

func kmp_search (String S, String W) {

    S.graphemes!
    W.graphemes!

    func kmp_table {
        var (pos, cnd, *T) = (1, 0, -1)
        for (nil; pos < W.len; (++pos; ++cnd)) {
            if (W[pos] == W[cnd]) {
                T[pos] = T[cnd]
            }
            else {
                T[pos] = cnd
                while ((cnd >= 0) && (W[pos] != W[cnd])) {
                    cnd = T[cnd]
                }
            }
        }
        T[pos] = cnd
        return T
    }

    var (k, T, *I) = (0, kmp_table())

    for (var j = 0; j < S.len; nil) {
        if (W[k] == S[j]) {
            ++j
            ++k
            if (k == W.len) {
                I << (j - k)
                k = T[k]
            }
        }
        elsif ((k = T[k]) < 0) {
            ++j
            ++k
        }
    }

    return I
}

var texts = [
    "GCTAGCTCTACGAGTCTA",
    "GGCTATAATGCGTA",
    "there would have been a time for such a word",
    "needle need noodle needle",
    "BharôtভাৰতBharôtভারতIndiaBhāratભારતBhāratभारतBhārataಭಾರತBhāratभारतBhārat"+
    "amഭാരതംBhāratभारतBhāratभारतBharôtôଭାରତBhāratਭਾਰਤBhāratamभारतम्Bārataபாரத"+
    "ம்BhāratamഭാരതംBhāratadēsamభారతదేశం",
    "InhisbookseriesTheArtofComputerProgrammingpublishedbyAddisonWesleyDKnu"+
    "thusesanimaginarycomputertheMIXanditsassociatedmachinecodeandassemblyl"+
    "anguagestoillustratetheconceptsandalgorithmsastheyarepresented",
    "Nearby farms grew a half acre of alfalfa on the dairy's behalf, with ba"+
    "les of all that alfalfa exchanged for milk.",
]

var pats = ["TCTA", "TAATAAA", "word", "needle", "ഭാരതം", "put", "and", "alfalfa"]

texts.each_kv {|k,v| say "text#{k} = #{v}" }; say ''

pats.each_kv {|k,v|
    var j = (k < 6 ? k : k-1)
    say ("Found '#{v}' in 'text#{j}' at indices ", kmp_search(texts[j], v))
}

Output:

text0 = GCTAGCTCTACGAGTCTA
text1 = GGCTATAATGCGTA
text2 = there would have been a time for such a word
text3 = needle need noodle needle
text4 = BharôtভাৰতBharôtভারতIndiaBhāratભારતBhāratभारतBhārataಭಾರತBhāratभारतBhāratamഭാരതംBhāratभारतBhāratभारतBharôtôଭାରତBhāratਭਾਰਤBhāratamभारतम्Bārataபாரதம்BhāratamഭാരതംBhāratadēsamభారతదేశం
text5 = InhisbookseriesTheArtofComputerProgrammingpublishedbyAddisonWesleyDKnuthusesanimaginarycomputertheMIXanditsassociatedmachinecodeandassemblylanguagestoillustratetheconceptsandalgorithmsastheyarepresented
text6 = Nearby farms grew a half acre of alfalfa on the dairy's behalf, with bales of all that alfalfa exchanged for milk.

Found 'TCTA' in 'text0' at indices [6, 14]
Found 'TAATAAA' in 'text1' at indices []
Found 'word' in 'text2' at indices [40]
Found 'needle' in 'text3' at indices [0, 19]
Found 'ഭാരതം' in 'text4' at indices [68, 138]
Found 'put' in 'text5' at indices [26, 90]
Found 'and' in 'text5' at indices [101, 128, 171]
Found 'alfalfa' in 'text6' at indices [33, 87]

Wren

This is based on the code here. The examples used are the same as in the Boyer-Moore_string_search#Wren task.

class KMP {
    static search(haystack, needle) {
        haystack = haystack.bytes.toList
        needle = needle.bytes.toList
        var hc = haystack.count
        var nc = needle.count
        var indices = []
        var i = 0 // index into haystack
        var j = 0 // index into needle
        var t = table_(needle)
        while (i < hc) {
            if (needle[j] == haystack[i]) {
                i = i + 1
                j = j + 1
            }
            if (j == nc) {
                indices.add(i - j)
                j = t[j-1]
            } else if (i < hc && needle[j] != haystack[i]) {
                if (j != 0) {
                    j = t[j-1]
                } else {
                    i = i + 1
                }
            }
        }
        return indices
    }

    static table_(needle) {
        var nc = needle.count
        var t = List.filled(nc, 0)
        var i = 1   // index into table
        var len = 0 // length of previous longest prefix
        while (i < nc) {
            if (needle[i] == needle[len]) {
               len = len + 1
               t[i] = len
               i = i + 1
            } else if (len != 0) {
                len = t[len-1]
            } else {
                t[i] = 0
                i = i + 1
            }
        }
        return t
    }
}

var texts = [ 
    "GCTAGCTCTACGAGTCTA",
    "GGCTATAATGCGTA",
    "there would have been a time for such a word",
    "needle need noodle needle",
"InhisbookseriesTheArtofComputerProgrammingpublishedbyAddisonWesleyDKnuthusesanimaginarycomputertheMIXanditsassociatedmachinecodeandassemblylanguagestoillustratetheconceptsandalgorithmsastheyarepresented",
    "Nearby farms grew a half acre of alfalfa on the dairy's behalf, with bales of all that alfalfa exchanged for milk."
]
var pats = ["TCTA", "TAATAAA", "word", "needle", "put", "and", "alfalfa"]
for (i in 0...texts.count) System.print("text%(i+1) = %(texts[i])")
System.print()
for (i in 0...pats.count) {
    var j = (i < 5) ? i : i-1
    System.print("Found '%(pats[i])' in 'text%(j+1)' at indices %(KMP.search(texts[j], pats[i]))")
}

Output:

text1 = GCTAGCTCTACGAGTCTA
text2 = GGCTATAATGCGTA
text3 = there would have been a time for such a word
text4 = needle need noodle needle
text5 = InhisbookseriesTheArtofComputerProgrammingpublishedbyAddisonWesleyDKnuthusesanimaginarycomputertheMIXanditsassociatedmachinecodeandassemblylanguagestoillustratetheconceptsandalgorithmsastheyarepresented
text6 = Nearby farms grew a half acre of alfalfa on the dairy's behalf, with bales of all that alfalfa exchanged for milk.

Found 'TCTA' in 'text1' at indices [6, 14]
Found 'TAATAAA' in 'text2' at indices []
Found 'word' in 'text3' at indices [40]
Found 'needle' in 'text4' at indices [0, 19]
Found 'put' in 'text5' at indices [26, 90]
Found 'and' in 'text5' at indices [101, 128, 171]
Found 'alfalfa' in 'text6' at indices [33, 87]