String Matching

Given a string and a pattern, your task is to count the number of positions where the pattern occurs in the string.

Example:

Input: text = "saippuakauppias", str = "pp"
Output: 2

Approach

Java

public class StringMatching {
    public static void main(String[] args) {
        String text = "saippuakauppias", str = "pp";

        System.out.println(stringMatching(text, str));

    }

    static int[] prefixArray(String s) {
        int n = s.length();
        int[] prefix = new int[n];
        for (int i = 1; i < n; i++) {
            int j = prefix[i - 1];
            while (j > 0 && s.charAt(i) != s.charAt(j))
                j = prefix[j - 1];
            if (s.charAt(i) == s.charAt(j))
                j++;
            prefix[i] = j;
        }
        return prefix;
    }

    static int stringMatching(String text, String str) {

        text = str + "#" + text;
        int[] v = prefixArray(text);
        int cnt = 0;
        for (int i = 0; i < v.length; i++) {
            if (v[i] == str.length())
                cnt++;
        }
        return cnt;
    }

}

C++

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

vector<int> prefixArray(string s)
{
    int n = s.length();
    vector<int> prefix(n);
    for (int i = 1; i < n; i++)
    {
        int j = prefix[i - 1];
        while (j > 0 && s[i] != s[j])
            j = prefix[j - 1];
        if (s[i] == s[j])
            j++;
        prefix[i] = j;
    }
    return prefix;
}
int stringMatching(string text, string str)
{

    text = str + "#" + text;
    vector<int> v = prefixArray(text);
    int cnt = 0;
    for (int i = 0; i < v.size(); i++)
    {
        if (v[i] == str.size())
            cnt++;
    }
    return cnt;
}
int main()
{
    string text = "saippuakauppias", str = "pp";

    cout << stringMatching(text, str) << "\n";

    return 0;
}