Maple's Blog.

Leetcode-28

Leetcode
字数统计: 1.2k阅读时长: 4 min
2019/04/09 Share

strStr-链接

实现的代码如下：

这是一道典型的字符串匹配题……直接用KMP算法然后就过了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
public:
    int strStr(string haystack, string needle) {
        //这里要考虑两种特殊的情况
        if (needle.size() == 0)
            return 0;
        if (haystack.size() == 0)
            return -1;
        //先获得next数组    
        getnext(&needle[0]);
        //接下来就是典型的KMP
        int Tlen=haystack.size();
        int Plen=needle.size();
        for(int i=0,j=0;i<Tlen;i++)
        {
            //当j>0的时候才有j回溯的机会，并且当前的模式串字符不等于主串的字符
            while(j>0&&haystack[i]!=needle[j])
            {
            //然后j回溯到next1[j-1]的位置，关于next数组不懂得可以详细看下百度的资料
                j=next1[j-1];
            }
            //考虑一个极端:模式串和主串一直匹配的情况，然后顺利匹配成功结束，然后这世界没那么多极端......所以就要用到上面的while循环
            if(haystack[i]==needle[j])
            {
                j++;
            }
            //当完全匹配成功后就直接返回当前的下标
            if(j==Plen)
                return i-j+1;
        }
        return -1;

    }
private:
    vector<int>next1;
    //其实这里就是一个如何得到next数组的函数，因为好像next在C++中是个关键字，所以我这里用到了next1数组
    void getnext(char *s)
    {
        next1=vector<int>(strlen(s)+1);
        //模式串的第一个字符的next值为0，因为没有东西可以匹配
        next1[0]=0;
        int k;
        //接着，从下标为1的位置开始，计算出next数组的值
        for(int i=1,k=0;i<strlen(s);i++)
        {
        //其实整个next数组最核心的地方还是这里，关于这里的理解说实话说起来有点多，我就写在后面吧
            while(k>0&&s[k]!=s[i])
            {
                k=next1[k-1];
            }
       //从下标为1开始，如果s[k]!=s[i]("ab"这种),那么next[1]也等于0，如果是s[k]==s[j](“aa”这种),那么next[1]就为1了，此时k++了
            if(s[k]==s[i])
                k++;
            next1[i]=k;
        }
    }
};

看这里⤵️

首先我们要搞清楚next数组的含义：

next数组的值是代表着字符串的前缀与后缀相同的最大长度,(不能包括自身)
1
2
3
4
while(k>0&&s[k]!=s[i])
           {
               k=next1[k-1];
           }

举个栗子，给了一个模式串“ABABAA”，我们得到的next数组的值应该是这样的

next[0]=0;

next[1]=0;

next[2]=1;

next[3]=2;

next[4]=3;

next[5]=1;

① :
next[0],next[1]我们可以手动模拟代码，然后很简单得出答案；

② :
那么如何求next[2]呢？此时的s[2]=’A’,s[0]=’A’,两个相等，所以next[2]=k++=1;如果这里s[2]!=’A’,不相等的话就是next[2]=0;

③ :
现在我们是已知next[0]=0,next[1]=0.next[2]=1的情况下了，然后现在要求next[3]，怎么办呢？

④ :
接着执行next[3]的计算，首先while循环里面只有一个条件满足k=1>0,而s[1]=s[3]=‘B’，所以我们直接让k++,next[3]=2;

⑤ :
接着我们计算next[4],现在的k=2,并且s[2]=’A’,s[i]=s[4]=’A’,不满足while的2个条件，所以又要让k++,则next[4]=3;

⑥ :
接着计算next[5],现在的k=3,s[3]=’B’,s[5]=’A’,两者不相同，那么执行while循环，接下来k的值就应该为next[k-1]了，为什么？

现在我给出两个字符串，一个是原来的模式串”ABABAA“，一个是m串”ABABAB“；我就将最后的s[5]由‘A’ 字符变成了‘B’，如果是‘B’字符的话，那么k又要加一，则next[5]=4;

现在按照真实情况来，为什么要k=next[k-1];是因为如果第下标为k的这个s[k]字符和现在的s[i]不同，我们就要看s[i]是不是能与s[k-1],也就是k前一位的字符匹配，如果能，在当前的k值的基础上加上一个1作为s[i]的next值，（这里的k值实际上是next[k+1],此时k位置后面的一个next数组的值）如果还不相同，继续让k往前一位挪，直到最后没有匹配的那么next[5]为0，途中有匹配的话就按照k位置的上一个位置的next数组的值加一个1。

最后结束next数组的计算。

说句实话，这个next数组的计算为什么要这样，真的是有点只可意会不可言传的意思，你要真的自己用自己的方法理解了才能做好题……此外还有一些推导公式，为什么在KMP算法中要让j回溯到next[j-1]的位置，如果不理解的可以去百度一下，看看这些知识点……

原文作者：Maple

原文链接：http://yoursite.com/2019/04/09/leetcode-28/

发表日期：April 9th 2019, 8:36:42 pm

更新日期：April 10th 2019, 7:01:02 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 首先我们要搞清楚next数组的含义：
    1. 1.1. next数组的值是代表着字符串的前缀与后缀相同的最大长度,(不能包括自身)
Total : 51
2019
Leetcode 算法与数据结构 C++ 洛谷