$ is a special character should not be present in pattern and text,

and T is text.

Build the Z array for concatenated string. In Z array, if Z value at any point is equal to pattern length, then pattern is present at that point.

Example:

Pattern P = "aab",  Text T = "baabaa"
The concatenated string is = "aab$baabaa"
Z array for the above concatenated string is {X, 1, 0, 0, 0, 3, 1, 0, 2, 1}.
Since the length of the pattern is 3, the value 3 in the Z array indicates the presence of the pattern.

How to construct Z array?

A simple solution involves two nested loops: the outer loop goes to every index, and the inner loop finds the length of the longest prefix matching the substring starting at the current index. This solution has a time complexity of O(n^2).

We can construct the Z array in linear time:

The idea is to maintain an interval [L, R] which is the interval with the maximum R such that [L,R] is a prefix substring (a substring which is also a prefix).

Steps for maintaining this interval are as follows:

If i > R, there is no prefix substring that starts before i and ends after i, so we reset L and R and compute a new [L, R] by comparing str[0..] to str[i..] and get Z[i] = R - L + 1.
If i <= R, let K = i - L. Now, Z[i] >= min(Z[K], R - i + 1) because str[i..] matches with str[K..] for at least R - i + 1 characters (they are in the [L, R] interval which we know is a prefix substring). Two sub-cases arise: a. If Z[K] < R - i + 1, there is no prefix substring starting at str[i] (otherwise Z[K] would be larger), so Z[i] = Z[K] and the interval [L, R] remains the same. b. If Z[K] >= R - i + 1, it is possible to extend the [L, R] interval. Thus, we set L as i and start matching from str[R] onwards to get a new R, then we update the interval [L, R] and calculate Z[i] = R - L + 1.

The algorithm runs in linear time because we never compare characters less than R. With matching, we increase R by one, so there are at most T comparisons. In the mismatch case, mismatches happen only once for each i (because of which R stops), leading to another at most T comparisons, making the overall complexity linear.

Code

[{"language":"Java","code":"public class Solution {\n    public int strStr(String haystack, String needle) {\n        String concat = needle + \"$\" + haystack;\n        int l = concat.length();\n        int[] Z = new int[l];\n        getZarr(concat, Z);\n\n        for (int i = 0; i < l; ++i) {\n            if (Z[i] == needle.length()) {\n                return i - needle.length() - 1;\n            }\n        }\n        return -1;\n    }\n\n    private void getZarr(String str, int[] Z) {\n        int n = str.length();\n        int L = 0, R = 0;\n\n        for (int i = 1; i < n; ++i) {\n            if (i > R) {\n                L = R = i;\n                while (R < n && str.charAt(R) == str.charAt(R - L)) {\n                    R++;\n                }\n                Z[i] = R - L;\n                R--;\n            } else {\n                int k = i - L;\n                if (Z[k] < R - i + 1) {\n                    Z[i] = Z[k];\n                } else {\n                    L = i;\n                    while (R < n && str.charAt(R) == str.charAt(R - L)) {\n                        R++;\n                    }\n                    Z[i] = R - L;\n                    R--;\n                }\n            }\n        }\n    }\n}","lang":"java"},{"language":"Python","code":"class Solution:\n    def strStr(self, haystack: str, needle: str) -> int:\n        concat = needle + \"$\" + haystack\n

Related Tags