Question

You have to perform the following tasks:

1- Write the name of best string matching algorithm in terms of time and space complexity.

2- Implement it in (c or c++)

3- Dry run it on following strings:

- String A=aaabaaaabbaaabcaaabd

- String B=aaabd

Deliverable in PDF file:

Code + Dry run + Code execution results using the above given strings.

Answer 1

ANSWER :-

(1). All string matching are good, it's all depends on what kind of search operation you are performing but in generally best algorithm for pattern searching is Knuth Morris Pratt (KMP) algrorithm ("In terms of its time and space complexity").

Time Complexity = O(n)

(2).

#include <iostream>
using namespace std; 
// implementing KMP algorithm
void KMPAlgo(string A, string B)
{
    int x = A.length();
    int y = B.length();
 
    // if B(Sub String) is an empty string
    if (y == 0)
    {
        cout << "Pattern found at index 0";
        return;
    }
 
    // if A's length is less than that of B's
    if (x < y)
    {
        cout << "Pattern not found";
        return;
    }
 
    // next[i] stores the index of next best partial match.
    int next[y + 1];
 
    for (int i = 0; i < y + 1; i++)
        next[i] = 0;
 
    for (int i = 1; i < y; i++)
    {
        int j = next[i + 1];
 
        while (j > 0 && B[j] != B[i])
            j = next[j];
 
        if (j > 0 || B[j] == B[i])
            next[i + 1] = j + 1;
    }
 
    for (int i = 0, j = 0; i < x; i++)
    {
        if (A[i] == B[j])
        {
            if (++j == y)
                cout << "Pattern found at index " << i - j + 1 << endl;
        }
        else if (j > 0) {
            j = next[j];
            i--;    // since i will be incremented in next iteration
        }
    }
}
 
//main function
int main()
{
    string String = "aaabaaaabbaaabcaaabd";
    string SubString = "aaabd";
 
    KMPAlgo(String, SubString);
 
    return 0;
}

(3).

String A=aaabaaaabbaaabcaaabd

String B=aaabd

Output :-