Count Prefix of a Given String solution leetcode

Code Solution: Count Prefix of a Given String in C++ for LeetCode

#include <iostream>
#include <vector>
using namespace std;

int countPrefix(string s) {
    int n = s.size();
    vector<int> pi(n);
    int ans = 0;
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) {
            j = pi[j - 1];
        }
        if (s[i] == s[j]) {
            j++;
        }
        pi[i] = j;
        ans += j;
    }
    return ans;
}

int main() {
    string s = "abab";
    cout << countPrefix(s) << endl;
    return 0;
}

Explanation:

• Include necessary libraries:
• #include <iostream> for input/output operations.

• #include <vector> for using vectors.

• Define the function countPrefix that takes a string s as input and returns an integer.

• Initialize variables:

• n as the size of the input string s.
• pi as a vector of integers of size n to store the prefix function values.

• ans to store the count of prefix occurrences.

• Iterate through the string:

• Start a loop from index 1 to n-1.
• Initialize j with the value of pi[i-1].
• While j is greater than 0 and the characters at positions i and j in the string s are not equal, update j to pi[j-1].
• If the characters at positions i and j are equal, increment j by 1.
• Update the value of pi[i] to j.

• Add the value of j to ans.

• Return the final count of prefix occurrences.

• In the main function:

• Initialize the string s with the input string "abab".
• Call the countPrefix function with string s as input and output the result.