Question

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Solution

First Solution

C++ (brute force):

class Solution {
public:
    int strStr(string haystack, string needle) {
        for(int i=0;;i++){
            for(int j=0;;j++){
                if(j==needle.length()) return i;
                if(i==haystack.length()) return -1;
                if(needle[j] != haystack[i+j]) break;
            }
        }
    }
};

result: time limit exceeded, so I make some changes to optimize the algorithm. I reduce operations in each iteration.

class Solution {
public:
    int strStr(string haystack, string needle) {
        int i = 0, j = 0,lenn = needle.length(),lenh = haystack.length();
        if (lenn == 0)  return 0;
        for(;i<=lenh-lenn;i++){
            for(j=0;;j++){
                if(j==lenn) return i;
                if(needle[j] != haystack[i+j]) break;
            }
        }
        return -1;
    }
};

Second Solution

• KMP
  A good interpretation of KMP(中文)

My Solution:

class Solution {
public:
    static vector<int> KMP;
    static int strStr(string haystack, string needle);
    static void calKMP(string needle);
};

vector<int> Solution::KMP;
int Solution::strStr(string haystack, string needle) {
    calKMP(needle);
    int i = 0, j = 0, lenn = needle.length(), lenh = haystack.length();
    for (i = 0;i<=lenh-lenn;) {
        for (j = 0;; j++) {
            if (j == lenn) return i;
            if (needle[j] != haystack[i + j]) {
                if (j == 0) i++;
                else i = i + (j - KMP[j-1]);             //根据Partial Match Table来确定i后移的位数
                break;
            }
        }
    }
    return -1;
}

void Solution::calKMP(string needle) {
    unordered_map<string, int> hash;              //用于前缀和后缀匹配
    int i = 0,j = 0,k = 0,max_num = 0,lenn = needle.length(); 
    for (; j < lenn;j++){
        max_num = 0;
        for (; k <= j; k++) {
            hash.insert({ needle.substr(0,k+1),k+1 });             //存入前缀
        }
        for (i=j; i > 0; i--) {
            unordered_map<string, int>::iterator it = hash.find(needle.substr(i, j-i+1));        //后缀与前缀匹配
            if (it != hash.end()) {
                max_num = max(it->second, max_num);                //取最大字串的字符数
            }        
            else continue;
        }
        KMP.push_back(max_num);                          //存入Partial Match Table
    }
}

I also got a time limit exceeded using this method, I think it has to do with the calKMP part but I haven't fixed it up yet. I'll work on that someday...

原文地址：我的主页文章