LeetCode28 实现strStr()(找到子串第一次出现的位置BF,KMP)

原题目

代码分析

使用c语言strstr

char *ch = strstr(haystack, needle) 得到当前位置

int strStr(char * haystack, char * needle){
    char * res = strstr(haystack, needle);
    return res!=NULL ? res-haystack : -1;
}

使用C++find

int index = haystack.find(needle) 得到当前位置

class Solution {
public:
    int strStr(string haystack, string needle) {
        return haystack.find(needle);
    }
};

BF

class Solution {
public:
    int strStr(string haystack, string needle) {
        int index_h = 0, index_n = 0;//haystack的下标位置,needle的下标位置
        while(index_h<haystack.size()&&index_n<needle.size()){
            if(haystack[index_h] == needle[index_n]){//如果相等,继续比较下一个
                index_h++;
                index_n++;
            }else{//如果不相等,则让haystack的下标移到上次起点的下一个,needle的下标从0开始
                index_h = index_h - index_n + 1;
                index_n=0;
                if(haystack.size() - index_h < needle.size()){//如果haystack剩余的字符少于needle的字符数,则不能找到
                    break;
                }
            }
        }
        if(index_n == needle.size()){//如果needle遍历到最后,说明查找到了
            return index_h - index_n;
        }
        return -1;
    }
};

KMP

class Solution {
public:
    void getNext(string n, vector<int>&next){
        next[0] = -1;
        int i = 0, j = -1;
        while(i<n.size()){
            if(j == -1|| n[i] == n[j]){
                i++;
                j++;
                next[i] = j;
            }else{
                j = next[j];
            }
        }
    }
    int KMP(string h, string n){
        vector<int>next(n.size()+1);
        getNext(n,next);
        int i = 0, j = 0;
        while(i < (int)h.size()&& j < (int)n.size()){
            if(j == -1 || h[i]==n[j]){
                i++;
                j++;
            }else{
                j = next[j];
            }
        }
        return j == n.size()?i-j: -1;
    }
    int strStr(string haystack, string needle) {
        return KMP(haystack, needle);
    }
};

本文地址：https://blog.csdn.net/weixin_44529350/article/details/107279765