How to implement the KMP algorithm in C#

How to implement the KMP algorithm in C

#KMP (Knuth-Morris-Pratt) algorithm is an efficient string matching algorithm used to match text strings Find the location of the pattern string in . Its core idea is to use the partial information that has been matched to avoid unnecessary comparisons.

The key to implementing the KMP algorithm is to construct a partial match table (Partial Match Table), also called the next array. This array records the length of the longest matching suffix substring of each prefix substring in the pattern string.

The following are the specific steps and code examples for implementing the KMP algorithm in C#:

Step 1: Build a partial matching table

1. Define a pattern with a size of the length of the pattern string Integer array next, and initialize next[0] = -1.
2. Define two pointers i and j, with initial values ​​0 and -1 respectively.
3. Determine whether i reaches the end of the pattern string. If not, perform the following steps:
   a. If j is equal to -1 or the current character is equal to the character corresponding to pointer j, then i and j are moved backward at the same time. , and next[i] = j.
   b. Otherwise, move the pointer j to the position of next[j] and continue matching.
4. Return the constructed partial matching table next.

The following is the code for how to implement the above steps:

private int[] BuildNext(string pattern)
{
    int[] next = new int[pattern.Length];
    next[0] = -1;
    int i = 0, j = -1;
    
    while (i < pattern.Length - 1)
    {
        if (j == -1 || pattern[i] == pattern[j])
        {
            i++;
            j++;
            next[i] = j;
        }
        else
        {
            j = next[j];
        }
    }
    
    return next;
}

Step 2: Use partial matching table for matching

1. Define two pointers i and j , pointing to the starting position of the text string and pattern string respectively.
2. Determine whether i and j have reached the end. If not, perform the following steps:
   a. If j is equal to -1 or the current character is equal to the character corresponding to pointer j, then i and j will move backward at the same time.
   b. Otherwise, move the pointer j to the position of next[j] and continue matching.
3. If the pointer j points to the end of the pattern string, it means the match is successful and the index of the starting position in the text string is returned.
4. If the match fails, -1 is returned.

The following is the code for how to implement the above steps:

private int KMP(string text, string pattern)
{
    int[] next = BuildNext(pattern);
    int i = 0, j = 0;
    
    while (i < text.Length && j < pattern.Length)
    {
        if (j == -1 || text[i] == pattern[j])
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];
        }
    }
    
    if (j == pattern.Length)
    {
        return i - j;
    }
    
    return -1;
}

By calling the KMP method and passing in the text string and pattern string, the matching result can be obtained.

The above are the steps and code examples on how to implement the KMP algorithm in C#. By utilizing partial matching tables, the KMP algorithm can effectively improve the efficiency of string matching, especially when processing large text strings and long pattern strings, with better performance.

The above is the detailed content of How to implement the KMP algorithm in C#. For more information, please follow other related articles on the PHP Chinese website!