String Algorithm

The provided code includes two functions: lps for computing the Longest Prefix Suffix (LPS) array and kmp for performing Knuth-Morris-Pratt (KMP) pattern matching.

1. lps computes the LPS array for a given pattern string. It uses a loop and two pointers (i and index) to compare characters and build the LPS values incrementally. The LPS values are stored in the vector v, which is then returned.
2. kmp is the KMP pattern matching function. It takes two strings, s (the text to search in) and pattern (the pattern to search for). It initializes pointers i and j and an ans variable to count pattern occurrences. It also calculates the LPS array using the lps function.

Inside a while loop, it compares characters of s and pattern. If a match is found, it increments both pointers. In case of a mismatch, it uses the LPS values to determine how much to shift j (the pattern pointer). When j equals the length of pattern, a pattern match is found, and ans is incremented. The j pointer is then adjusted using the LPS values.

This code efficiently counts occurrences of pattern in s using the KMP algorithm and the precomputed LPS array.

vector<int> lps(string pattern)
{
    int n = pattern.size();
    vector<int> v(n);
    int index = 0;
 
    for (int i = 1; i < n;)
    {
        if (pattern[i] == pattern[index])
        {
            v[i] = index + 1;
            i++;
            index++;
        }
        else
        {
            if (index)
                index = v[index - 1];
            else
            {
                v[i] = 0;
                i++;
            }
        }
    }
    return v;
}
 
int kmp(string s, string pattern)
{
    int n = s.size(), m = pattern.size();
    int i = 0, j = 0;
    int ans = 0;
 
    vector<int> v = lps(pattern);
 
    while (i < n)
    {
        if (s[i] == pattern[j])
        {
            i++;
            j++;
        }
        else
        {
            if (j)
                j = v[j - 1];
            else
                i++;
        }
 
        if (j == m) //to count how many pattern match
        {
            ans++;
            j = v[j - 1];
        }
    }
 
    return ans;
}