Implement strStr() Solutions in C++

// Source : https://oj.leetcode.com/problems/implement-strstr/
// Author : Hao Chen
// Date   : 2014-07-19



#include <stdio.h>
#include <stdlib.h>
#include <time.h>

char *strStr1(char *haystack, char *needle);
char *strStr2(char *haystack, char *needle);

char *strStr(char*haystack, char *needle) {
    if (random()%2){
        printf("---KMP---\n");
        return strStr1(haystack, needle);
    }
    printf("---brute-force---\n");
    return strStr2(haystack, needle);
}
//KMP
char *strStr1(char *haystack, char *needle) {
    if(!haystack || !needle ) {
        return NULL;
    }
    if (!*needle ) {
        return haystack;
    }

    char *ph = haystack;
    char *pn = needle;
    for( ;*ph && *pn ; ph++, pn++ );

    //len(haystack) < len(needle)
    if (!*ph && *pn){
        return NULL;    
    }

    for(ph=ph-1; *ph; haystack++, ph++) {
        char *q=needle;
        char *p=haystack;
        int n=0;
        while(*q && *p && *p==*q){
            p++; q++;
            if (n==0 && *p == *needle){
                n = p - haystack;
            }
        }
        if (!*q){
            return haystack;
        }
        haystack += (n>0 ? n-1 : n);
    }
    return NULL;
}

//brute-force
char *strStr2(char *haystack, char *needle) {

    if(!haystack || !needle ) {
        return NULL;
    }
    if (!*needle ) {
        return haystack;
    }

    char *ph = haystack;
    char* pn = needle;
    for( ;*ph && *pn ; ph++, pn++ );

    //len(haystack) < len(needle)
    if (!*ph && *pn){
        return NULL;    
    }
    ph--;

    for( ; *ph; haystack++, ph++) {
        char *q=needle;
        char *p=haystack;
        while(*q && *p && *p==*q){
            p++; q++;
        }
        if (!*q){
            return haystack;
        }
    }

    return NULL;
}

int main(int argc, char** argv)
{
    srand(time(0));
    const char* haystack = "mississippi";
    const char* needle = "issi";
    printf("%s, %s : %s\n", haystack, needle, strStr((char*)haystack, (char*)needle));

    haystack = "mississippi";
    needle = "issip";
    printf("%s, %s : %s\n", haystack, needle, strStr((char*)haystack, (char*)needle));


    haystack = "babbbbbabb";
    needle = "bbab";
    printf("%s, %s : %s\n", haystack, needle, strStr1((char*)haystack, (char*)needle));

    if (argc>2){
        haystack = argv[1];
        needle = argv[2];
        printf("%s, %s : %s\n", haystack, needle, strStr((char*)haystack, (char*)needle));
    }
    
    return 0;
}

class Solution {
public:
    int strStr(char *haystack, char *needle) {
        if (!*haystack && !*needle) return 0;
        char *p = haystack;
        while (*p) {
            char *p1 = p, *p2 = needle;
            while (*p1 && *p2 && *p1 == *p2) {
                ++p1;
                ++p2;
            }
            if (!*p2) return p-haystack;
            else if (!*p1) break;
            ++p;
        }
        return -1;
    }
};

/// Source : https://leetcode.com/problems/implement-strstr/
/// Author : liuyubobobo
/// Time   : 2018-03-06

#include <iostream>

using namespace std;


/// Naive implementation
/// Time Complexity: O(n * m)
/// Sapce Complexity: O(1)
class Solution {
public:
    int strStr(string haystack, string needle) {

        int n = haystack.size(), m = needle.size();
        for(int i = 0 ; i <= n - m ; i ++){
            int j = 0;
            for(j = 0 ; j < needle.size() ; j ++)
                if(needle[j] != haystack[j + i])
                    break;
            if(j == needle.size())
                return i;
        }
        return -1;
    }
};


int main() {

    cout << Solution().strStr("hello", "ll") << endl;
    cout << Solution().strStr("aaaaa", "bba") << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/implement-strstr/
/// Author : liuyubobobo
/// Time   : 2019-03-12

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;


/// Rabin-Karp
/// Time Complexity: O(n * m)
/// Sapce Complexity: O(m)
class Solution {

private:
    const int MOD = 1e9 + 7;
    const int base = 256;

public:
    int strStr(string haystack, string needle) {

        if(needle == "") return 0;
        if(haystack == "") return -1;

        int n = haystack.size(), m = needle.size();
        if(n < m) return -1;

        int h = 1, txthash = 0, patternhash = 0;
        for(int i = 0; i < m - 1; i ++){
            h = h * 256ll % MOD;
            txthash = (txthash * 256ll + haystack[i]) % MOD;
            patternhash = (patternhash * 256ll + needle[i]) % MOD;
        }
        patternhash = (patternhash * 256ll + needle[m - 1]) % MOD;

        for(int i = m - 1; i < n; i ++){
            txthash = (txthash * 256ll + haystack[i]) % MOD;
            if(txthash == patternhash && same(haystack, i - m + 1, i, needle))
                return i - m + 1;

            txthash -= haystack[i - m + 1] * (long long)h % MOD;
            if(txthash < 0) txthash += MOD;
        }
        return -1;
    }

private:
    bool same(const string& s, int start, int end, const string& t){
//        assert(end - start + 1 == t.size());
        for(int i = start; i <= end; i ++)
            if(s[i] != t[i - start])
                return false;
        return true;
    }
};


int main() {

//    cout << Solution().strStr("hello", "ll") << endl; // 2
    cout << Solution().strStr("aaaaa", "bba") << endl; // -1
//    cout << Solution().strStr("mississippi", "issip") << endl; // 4

    return 0;
}

/// Source : https://leetcode.com/problems/implement-strstr/
/// Author : liuyubobobo
/// Time   : 2019-03-11

#include <iostream>
#include <vector>

using namespace std;


/// KMP based on lps
/// Time Complexity: O(n + m)
/// Sapce Complexity: O(m)
class Solution {
public:
    int strStr(string haystack, string needle) {

        if(haystack == "") return needle == "" ? 0 : -1;
        if(needle == "") return 0;

        int n = haystack.size(), m = needle.size();
        vector<int> lps = getLPS(needle, m); // longest proper prefix which is also suffix

        int i = 0, j = 0;
        while(i < n){

            if(haystack[i] == needle[j]) {
                i++, j++;

                if (j == needle.size())
                    return i - needle.size();
            }

            else if(j) j = lps[j - 1] ;
            else i ++;
        }
        return -1;
    }

private:
    vector<int> getLPS(const string& pattern, int m){

        vector<int> lps(m, 0);
        // lps[0] = 0;

        int len = 0;
        int i = 1;
        while(i < m)
            if(pattern[i] == pattern[len])
                lps[i ++] = ++ len;

            // trick part
            // a great explanation:
            // https://leetcode.com/problems/implement-strstr/discuss/13160/detailed-explanation-on-building-up-lps-for-kmp-algorithm
            else if(len) len = lps[len - 1]; // len --
            else i ++;
        return lps;
    }
};


int main() {

    cout << Solution().strStr("hello", "ll") << endl; // 2
    cout << Solution().strStr("aaaaa", "bba") << endl; // -1
    cout << Solution().strStr("mississippi", "issip") << endl; // 4

    return 0;
}

/// Source : https://leetcode.com/problems/implement-strstr/
/// Author : liuyubobobo
/// Time   : 2019-03-12

#include <iostream>
#include <vector>

using namespace std;


/// KMP based on lps
/// Another way to compute lps, maybe more intuitive :-)
/// See here for details:
/// https://www.coursera.org/lecture/algorithms-on-strings/computing-prefix-function-5lDsK
///
/// Time Complexity: O(n + m)
/// Sapce Complexity: O(m)
class Solution {
public:
    int strStr(string haystack, string needle) {

        if(haystack == "") return needle == "" ? 0 : -1;
        if(needle == "") return 0;

        int n = haystack.size(), m = needle.size();
        vector<int> lps = getLPS(needle, m); // longest proper prefix which is also suffix

        int i = 0, j = 0;
        while(i < n){

            if(haystack[i] == needle[j]) {
                i++, j++;

                if (j == needle.size())
                    return i - needle.size();
            }

            else if(j) j = lps[j - 1] ;
            else i ++;
        }
        return -1;
    }

private:
    vector<int> getLPS(const string& pattern, int m){

        vector<int> lps(m, 0);
        // lps[0] = 0;

        int len = 0;
        for(int i = 1; i < m; i ++){
            while(len && pattern[i] != pattern[len])
                len = lps[len - 1];

            if(pattern[i] == pattern[len])
                lps[i] = ++ len;
        }
        return lps;
    }
};


int main() {

    cout << Solution().strStr("hello", "ll") << endl; // 2
    cout << Solution().strStr("aaaaa", "bba") << endl; // -1
    cout << Solution().strStr("mississippi", "issip") << endl; // 4

    return 0;
}

/// Source : https://leetcode.com/problems/implement-strstr/
/// Author : liuyubobobo
/// Time   : 2019-03-12

#include <iostream>
#include <vector>

using namespace std;


/// KMP based on DFA
///
/// Time Complexity: O(m * all_characters + n)
/// Sapce Complexity: O(m * all_characters)
class Solution {
public:
    int strStr(string haystack, string needle) {

        if(needle == "") return 0;
        if(haystack == "") return -1;

        int n = haystack.size(), m = needle.size();
        vector<vector<int>> dfa(256, vector<int>(m + 1, 0));

        // dfa construction
        dfa[needle[0]][0] = 1;
        int lps = 0;
        for(int state = 1; state < m; state ++){
            for(int c = 0; c < 256; c ++)
                dfa[c][state] = dfa[c][lps];

            dfa[needle[state]][state] = state + 1;

            lps = dfa[needle[state]][lps];
        }

        int state = 0;
        for(int i = 0; i < n; i ++){
            state = dfa[haystack[i]][state];
            if(state == m) return i - m + 1;

        }
        return -1;
    }
};


int main() {

    cout << Solution().strStr("hello", "ll") << endl; // 2
    cout << Solution().strStr("aaaaa", "bba") << endl; // -1
    cout << Solution().strStr("mississippi", "issip") << endl; // 4

    return 0;
}

/// Source : https://leetcode.com/problems/implement-strstr/
/// Author : liuyubobobo
/// Time   : 2019-03-12

#include <iostream>
#include <vector>

using namespace std;


/// BM Algorithm
/// Only bad character heuristic is used
///
/// Time Complexity: O(m * all_characters + n)
/// Sapce Complexity: O(m * all_characters)
class Solution {
public:
    int strStr(string haystack, string needle) {

        if(needle == "") return 0;
        if(haystack == "") return -1;

        int n = haystack.size(), m = needle.size();
        vector<int> bad(256, -1); // last occurrence of every character
        for(int i = 0; i < m; i ++)
            bad[needle[i]] = i;

        int i = 0;
        while(i <= n - m){

            int j = m - 1;
            for(; j >= 0; j --)
                if(needle[j] != haystack[i + j])
                    break;

            if(j < 0) return i;
            if(bad[haystack[i + j]] < 0)
                i += j + 1;
            else
                i += max(1, j - bad[haystack[i + j]]);
        }
        return -1;
    }
};


int main() {

    cout << Solution().strStr("hello", "ll") << endl; // 2
    cout << Solution().strStr("aaaaa", "bba") << endl; // -1
    cout << Solution().strStr("mississippi", "issip") << endl; // 4

    return 0;
}