Simple C++ solution using Z-function, run in O(n) time


  • 1
    S

    Method Z-function: we calculat for each argument in string the maximum same prefics and prefics frim that position^
    For 'abcdabscabcdabia' Z-function will be : Z(abcdabscabcdabia)=[16,0,0,0,2,0,0,0,6,0,0,0,2,0,0,1].
    So my solution used this method for needle + '#' + haystack;

    class Solution {
    public:
        int strStr(string haystack, string needle) {
            if (!needle.size()) return 0;
            string combo = needle + '#' + haystack;
            vector<int> z(combo.size());
            int high = 0, it = 0;
            for (int i = 1; i < combo.size(); ++i) {
                high = max(high, i);
                if (high > i && z[i - it] + i != high) {
                    z[i] = min(z[i - it], high - i);
                } else {
                    it = i;
                    while(high < combo.size() && combo[high] == combo[high - i]) {
                        high++;
                    }
                    z[i] = high - i;
                    if (z[i] == needle.size()) {
                        return i - needle.size() - 1;
                    }
                }
            }
            return -1;
            
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.