题目

Implement strStr().

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

Update (2014-11-02):

The signature of the function had been updated to return the index instead of the pointer. If you still see your function signature returns a char * or String, please click the reload button to reset your code definition.

分析

这是一道模式匹配算法。给定两个字符串haystack与needle，给出needle在haystack全然匹配的首位置坐标（从0開始）。

这道题在数据结构中有解说，除了開始的简单模式匹配算法BF算法，还给出了改进后的KMP经典算法。以下分别用这两个算法实现。

AC代码

class Solution {

public:

    //简单模式匹配算法（BF算法）

    int strStr(string haystack, string needle) {

        int len = strlen(haystack.c_str()), nl = strlen(needle.c_str());

        int i = 0, j = 0;

        while (i < len && j < nl)

        {

            if (haystack[i] == needle[j])

            {

                i++;

                j++;

            }

            else{

                i = i - j + 1;

                j = 0;

            }//else

        }//while

        if (j == nl)

            return i - nl;

        else

            return -1;

    }

};

KMP算法实现

class Solution {

public:

    //简单模式匹配算法（BF算法）

    int strStr(string haystack, string needle) {

        int len = strlen(haystack.c_str()), nl = strlen(needle.c_str());

        int i = 0, j = 0;

        while (i < len && j < nl)

        {

            if (haystack[i] == needle[j])

            {

                i++;

                j++;

            }

            else{

                i = i - j + 1;

                j = 0;

            }//else

        }//while

        if (j == nl)

            return i - nl;

        else

            return -1;

    }

    //从字符串haystack的第pos个位置開始匹配

    int KMP(const string &haystack, const string &needle, int pos)

    {

        int len = strlen(haystack.c_str()), nl = strlen(needle.c_str());

        int i = pos, j = 0;

        int *n = Next(needle);

        while (i < len && j < nl)

        {

            if (j == -1 || haystack[i] == needle[j])

            {

                i++;

                j++;

            }

            else{

                j = n[j];

            }//else

        }//while

        if (j == nl)

            return i - nl;

        else

            return -1;

    }

    int* Next(const string &s)

    {

        int i = 0, j = -1;

        int next[500] ;

        int len = strlen(s.c_str());

        next[0] = -1;;

        while (i < len)

        {

            while (j >-1 && s[i] != s[j])

                j = next[j];

            i++;

            j++;

            if (s[i] == s[j])

                next[i] = next[j];

            else

                next[i] = j;

        }//while

        return next;

    }

};

GitHub測试程序源代码