Question:

How to use Search Pattern (KMP-Algorithm) using C++

Summary

We will implement the Knuth-Morris-Pratt (KMP) algorithm that helps you search string. This will allow you to search for occurrence patterns in a text efficiently.

The following is a brief overview of the KMP algorithm:

This algorithm helps preprocess the pattern and allows you to create a prefix function (‘kmp’ array). This defines the length of the longest proper prefix (which is also a suffix).

After this, it scans the text string and compares the characters of the text and the pattern. To avoid unnecessary comparison it uses the prefix function.

We will return -1 inside the vector in case no match is found and avoid wrapping this in a vector.

Solution

#include <vector>

#include <string>

using namespace std;

class Solution {

public:

vector<int> search(string pat, string txt) {

vector<int> kq;

int lenPat = pat.size();

int lenTxt = txt.size();

vector<int> kmp(lenPat, 0);

int k = 0;

// Preprocessing pattern

for (int i = 1; i < lenPat; ++i) {

while (k > 0 && pat[k] != pat[i])

k = kmp[k-1];

if (pat[k] == pat[i]) {

kmp[i] = k + 1;

++k;

} else {

kmp[i] = 0;

}

// Searching pattern in text

int q = 0;

for (int i = 0; i < lenTxt; ++i) {

while (q > 0 && pat[q] != txt[i])

q = kmp[q-1];

if (pat[q] == txt[i]) {

if ((q + 1) == lenPat) {

kq.push_back(i - lenPat + 1);

}

++q;

}

// Return -1 if no match found

if (kq.empty())

kq.push_back(-1);

return kq;

}

};

Now, the function of the above code will return a vector with -1. This will not contain the position where the different patterns is found in the text.

>How to check whether string is palindrome or not using C++

>How to determine the smallest possible size of a vertex cover using C++

>How to reverse the first K elements of queue using C++

>How to find duplicate rows in a binary matrix using C++

>How to find the total number of special sequences possible using C++

>How to Reverse array in groups? C++

>How to represent the maximum value in knapsack using C++