Data Structure Lab Report 3 – Using KMP Algorithm for String Search

WARNING

Experiment Objective:

This experiment aims to analyze and test the implementation of the KMP algorithm and explore its application in string searching.

Experiment Content:

a. Problem Analysis:

• How to construct the Longest Prefix Suffix (LPS) array to improve search efficiency?
• How to perform matching in the text string using the LPS array to avoid unnecessary character comparisons?
• How to design an algorithm to search for a pattern string?

b. Algorithm Design:

The KMP algorithm involves the following key steps:

• Constructing the LPS array: The computeLPSArray function calculates the LPS array for the pattern string, which indicates the longest matching length of prefixes and suffixes at each position in the pattern.
• Performing matching in the text: The KMPSearch function executes pattern matching in the text string. It utilizes the LPS array to backtrack intelligently, thereby improving search efficiency.

c. Data Structure Design:

In this experiment, the following data structures were used:

• Strings: To represent the text and pattern strings.
• Vectors: To store the LPS array.
• Integer variables: To track indices during the matching process.

d. Debugging Process:

While writing and testing the code, some potential issues such as logical errors or edge cases were encountered. Careful debugging was required to ensure the algorithm’s correctness and performance. By step-by-step debugging and printing intermediate results, the code was verified to correctly identify the positions of pattern matches in the text.

e. Output Results:

Below are some example output results:

• When the text string is "ABABDABACDABABCABAB" and the pattern string is "ABABCABAB", the KMP algorithm locates the pattern in the text at:

  Match found at index 10  
  

• When both the text and pattern strings are provided by the user, the KMP algorithm searches for the user-specified pattern in the given text and outputs the matching positions.

f. Source Code:

#include<bits/stdc++.h>
using namespace std;

// Computes the Longest Prefix Suffix (LPS) array for the pattern
void computeLPSArray(const string& pattern, vector<int>& lps) {
    int length = 0;  // Length of the previous longest prefix suffix

    lps[0] = 0;  // lps[0] is always 0

    int i = 1;

    while (i < pattern.length()) {
        if (pattern[i] == pattern[length]) {
            length++;
            lps[i] = length;
            i++;
        } else {
            if (length != 0) {
                length = lps[length - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
}

// Searches for the pattern in the text using the KMP algorithm
void KMPSearch(const string& text, const string& pattern) {
    int m = pattern.length();
    int n = text.length();

    vector<int> lps(m);
    computeLPSArray(pattern, lps);

    int i = 0;  // Index for text[]
    int j = 0;  // Index for pattern[]

    while (i < n) {
        if (pattern[j] == text[i]) {
            i++;
            j++;
        }

        if (j == m) {
            // Pattern found, print the starting index
            cout << "Match found at index " << i - j << endl;
            j = lps[j - 1];
        } else if (i < n && pattern[j] != text[i]) {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
}

// int main() {
//     string text = "ABABDABACDABABCABAB";
//     string pattern = "ABABCABAB";

//     KMPSearch(text, pattern);

//     return 0;
// }


int main() {
    string text;
    string pattern;
    cin>>text;
    cin>>pattern;

    KMPSearch(text, pattern);

    return 0;
}