kmp

Documentation

Overview

Package kmp implements the Knuth-Morris-Pratt (KMP) algorithm specialized for matching lines of text. Instead of searching for a pattern of characters within a string, this implementation of KMP operates on sequences of lines. The algorithm preprocesses the pattern to identify prefixes that match suffixes at each point in the pattern (the "partial match" table, or "failure function"). Using this information, the algorithm speeds up the search by skipping non-matching positions more efficiently. This avoids the less efficient backtracking characteristic of the naive search algorithm.

Index

• func KMPSearch(text []string, pattern []string) int

Functions

func KMPSearch

func KMPSearch(text []string, pattern []string) int

KMPSearch performs the KMP pattern searching algorithm on lines of text. It searches for the occurrences of a 'pattern' within the 'text', both represented as slices of strings. Each string in these slices is a line of text. The function prints the starting index of each match found in the 'text'. If no match is found, it produces no output.

The search efficiency is improved by leveraging the LPS array, which allows the algorithm to skip non-matching characters without having to backtrack. This mechanism helps in avoiding unnecessary comparisons, speeding up the pattern-matching process.

Parameters:

• text ([]string): A slice of strings, where each string is a line of text, representing the text to be searched.
• pattern ([]string): A slice of strings, where each string is a line of text, representing the pattern to be searched for.

Returns:

(int): The index of the first match found in the 'text', or -1 if no match is found.