一起刷leetcode(28):Implement strStr()


问题:28.Implement strStr()
来源:https://leetcode.com/problems/implement-strstr/
问题描述:

Implement strStr().

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

青原行思 - Crazy about ML!

赞同来自: 星空被仰望


KMP Algorithm,时间复杂度O(m+n),m,n分别为待匹配字符串与模式字符串的长度,已AC.
/*--------------------------
* Date:2015-03-11
* Author:qingyuanxingsi
* Title:28.Implement strStr()
* Link:https://leetcode.com/problems/implement-strstr/
* Result:AC
* Idea:KMP Algorithm
*/
class Solution {
public:
    int strStr(char *haystack, char *needle) {
        string target = haystack,pattern = needle;
        vector<int> prefix(pattern.size()+1,0);
        calPrefix(prefix,pattern);
        int x = 0;
        int count = 0;
        int index = 0;
        int pos = target.size()-pattern.size()+1;
        while(x<=pos){
            for(int i=index;i<pattern.size();i++){
                if(target[x+i] == pattern[i]){
                    count++;
                }
                else{
                    break;
                }
            }
            if(count==pattern.size()){
                return x;
            }
            if(count==0){
                x++;
            }
            else{
                x = x + count - prefix[count];
            }
            index = prefix[count];
            count = prefix[count];
        }
        return -1;
    }

    void calPrefix(vector<int> &prefix,string pattern){
        for(int i=1;i<pattern.size();i++){
            int temp = prefix[i];
            while(pattern[temp]!=pattern[i] && temp>0){
                temp = prefix[temp];
            }
            if(pattern[temp]==pattern[i]){
                prefix[i+1] = temp+1;
            }
        }
    }
};

要回复问题请先登录注册

收藏七月在线,一起向大牛进阶

ctrl+D或command+D可以快速收藏哦~