[Solved] How to write a program that returns number of occurrences of a string in another string? [closed]

Question

This question can be simply solved by using z-function in linear time.

int NumberOfcopies(String t, String h){
    // t = the first string i.e "ooo"
    // h = the second string i.e "wooooooooooooooooooooow"

    String s = t + "$" + h; // adding a sentinel character in between
    int n = s.length(); // length of new string
    int[] z = new int[n]; // z array

    // Code ref : http://e-maxx-eng.github.io/string/z-function.html
    int l = 0, r = 0;
    for (int i = 1; i < n; i++){
        if (i <= r)
            z[i] = Math.min(r - i + 1, z[i - 1]);
        while (i + z[i] < n && s.charAt(z[i]) == s.charAt(i + z[i]))
            ++z[i];
        if (i + z[i] - 1 > r){
            l = i;
            r = i + z[i] - 1;
        }
    }

    //checking for all the occurance of string t in string h
    int res = 0;
    for (int i = t.length() + 1; i < n; ){
        if (z[i] == t.length()){
            //A copy is found so skip next t.length chars
            i += t.length();
            ++res; 
        }
        else ++i;
    }
    System.out.println("Number of Occurance : " + res);
    return res;
}

The Z-function for this string is an array of length n where
the i-th element is equal to the greatest number of characters
starting from the position i that coincide with the first
characters of s.

This can be exploited to find the number of occurrences of a string t in another string h. Suppose we join the string t and h with a sentinel character in between (Sentinel character is a character that does not occur in either of the strings) to form a new string s.

Lets us calculate the z function in array z[].

Now lets start searching from the character after the sentinel character i.e. the characters of string h. For i-th character in string h ( such that i-th character belongs to string s) if z[i] equals to length of string t (the pattern) then it implies that starting from i-th char, the t.length() chars are same as the first t.length() chars of string s which is what the string t equals.

example :
t = ab
h = aaabaab

s = a b $ a a a b a a b
z = 0 0 0 1 1 2 0 1 2 0
i = 0 1 2 3 4 5 6 7 8 9

for i = 5 we can see that z[i] == t.length(), that means we found a copy. Now to prevent Overlapping solutions, we skip the t.length() chars hence now i = 7

continuing this will get you the result.

Accepted Answer