No.28 Implement strStr()

No.28 Implement strStr()

Implement strStr().

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

分析：

　　很经典的字符串匹配问题，若可以匹配，返回模式串在字符串中首次出现的下标；否则返回-1

　　最容易想到的就是暴力破解了，但复杂度高，肯定不是首选。

　　再就是经典的KMP算法，其实，之前看过好多次，但总是理解不了，后来就不了了之，这次看懂了，记录下。

KMP：

　　对于不懂KMP算法的人来说，先看看http://kb.cnblogs.com/page/176818/，对KMP有整体把握之后， 再看http://v.youku.com/v_show/id_XNzQzMjQ1OTYw.html视频可以很好的理解以下代码：

 

class Solution
{
public:
    int strStr(string haystack, string needle)
    {//字符串搜索匹配：返回needle在haystack中首次出现的下标；若未出现，返回-1
        return KMP(haystack, needle);
    }

    //目的：计算部分匹配表，即next数组
    //输入：pattern模式串，next为next数组
    void getNext(string pattern, int next[])
    {
        int m = pattern.size();
        if(m==0)
            return;

        next[0] = -1;//表示的是0之前的串的前缀后缀相同的最大位数
        int index,j;
        for(int i=1; i<m; i++)
        {//next[i]其实表示的是，0~i-1这个字符串的最大相同前缀串和后缀串的长度
            j = i-1;
            index = next[j];
            while(index >=0 && pattern[index] != pattern[j])
                index = next[index];

            if(index<0)
                next[i] = 0;
            else//pattern[index] == pattern[j]
                next[i] = index+1;
        }
    }

    //KMP算法
    //输入：text文本，pattern模式串；输出：成功则返回第一次匹配的位置；失败则返回-1
    int KMP(string text, string pattern)
    {
        int n = text.size();
        int m = pattern.size();
        if(n==0 && m==0)
            return 0;//根据题意，返回0!!
        if(m==0)
            return 0;//根据题意，返回0!!
        int *next = new int[m];
        getNext(pattern,next);

        int i=0, j = 0;
        while(i<n)
        {
            if(j==-1 || text[i] == pattern[j])
            //j==-1说明text[i]开头的字符串不可能和pattern匹配，所以text直接到下一个字符去
            {
                i++;
                j++;
            }
            else
                j = next[j];
            if(j == m)//!!!匹配成功
                return i-j;
        }

        delete[] next;
        return  -1;
    }        
};
int main()
{
    Solution sol;

    cout << sol.strStr("abaabcabaddsacbads","abaabcaba")<<endl;
    cout << sol.strStr("BBCABCDABABCDABCDABDE","ABCDABD")<<endl;
    cout << sol.strStr("abcdefs","adg")<<endl;
    cout << sol.strStr("abcdefd","ebc")<<endl;
    cout << sol.strStr("","ebc")<<endl;
    return 0;
}

 求解next数组的另一种方法：

    //目的：计算部分匹配表，即next数组
    //输入：pattern模式串，next为next数组
    void getNext(string pattern, int next[])
    {
        int m = pattern.size();
        if(m==0)
            return;

        next[0] = -1;//表示的是0之前的串的前缀后缀相同的最大位数

        int i=0,j=-1;//注意j=-1
        while(i < m-1)//范围控制到m-1
        {
            if(j==-1 || pattern[i] == pattern[j])
            {
                i++;
                j++;
                next[i] = j;
            }
            else
                j=next[j];
        }
            
    }

 暴力法：leetcode超时

class Solution
{
public:
    int strStr(string haystack, string needle)
    {//字符串搜索匹配：返回needle在haystack中首次出现的下标；若未出现，返回-1
     //暴力法
        int n = haystack.size();//主串大小
        int m = needle.size();//模式串大小

        if(m == 0)
            return 0;

        int pn = 0;//指示主串下标
        int pm = 0;//指示模式串串下标
        int cur;//指示当前次匹配主串开始的位置，若匹配，则返回
        while(pn < n)
        {
            while(pn<n && haystack[pn] != needle[pm])
                pn++;
            cur = pn;//找到与模式串首位置相同的位置，然后依次匹配
            pm++;
            pn++;
            while(pn<n && pm<m )
            {
                if(haystack[pn] != needle[pm])
                    break;
                pn++;
                pm++;
            } 

            if(pm == m)
                return cur;
            else
            {
                pn = cur+1;
                pm = 0;
            }
        }
        return -1;
    }