LeetCode 28: Find the Index of the First Occurrence in a String

心路历程

一开始迅猛完成了一个版本，然后忽略了这种情况

"mississippi"
"issip"

这样我会第一个在ssippi第二个在issip这样就找不到了

class Solution {
public:
    int strStr(string haystack, string needle) {
        /* find the first needle in haystack */
        int ret = -1, pos = 0;
        int needle_len = needle.size();
        //bool sign = false;
        for(int i = 0; i < haystack.size(); ++i)
        {
            if(haystack[i] == needle[pos])
            {
                if(pos == needle_len - 1) return i - needle_len + 1;
                printf("pos= %d\n",pos);
                ++pos;
            }
            else{
                pos = 0;
            }
        }
        return -1;
    }
};

So how to solve that problem??

经典的字符串单模匹配的模型
查找算法：

1. 暴力
2. Knuth-Morris-Pratt 算法
3. Boyer-Moore 算法
4. Sunday

暴力

就是把所有的都遍历一遍，不是像我version0那样。是for i每一个i都是一个检验的开头

实现

我的实现

class Solution {
public:
    int strStr(string haystack, string needle) {
        /* find the first needle in haystack */
        int ret = -1, pos = 0;
        int needle_len = needle.size();
        for(int i = 0; i < haystack.size(); ++i)
        {
            bool temp = true;
            for(int pos = 0; pos < needle_len; ++pos)
            {
                if(needle[pos] != haystack[i+pos])
                {
                    temp = false;
                    break;
                }
            }  
            if(temp) return i;
        }
        return -1;
    }
};

ps.哈哈哈哈哈我保证自己写之前没看官方题解，几乎长得一模一样了。
but这确实比较复杂，让我继续学习。
//暂时休息，明天再来

KMP算法

求真前缀真后缀的对数。
、、留坑

求前缀函数

Sunday解法

• haystack：长string；
  长度：len
• needle：要在长string里找到needle的最初位置；
  长度：nlen

从haystack[0]开始配对，当前位置i如果haystack[i:i+nlen]不匹配，查看haystack[i+neln]是否是needle中其中一个字母

• 是：i = i + 偏移表；
• 不是：与haystack[i+nlen+1]匹配；

偏移表

存储每一个在needle中出现的字符。在needle中出现的最右位置到尾部的距离+1。
举例needle=this

• t：偏移位= 3+1 = 4；
• h：偏移位= 2+1 = 3；
• i：偏移位= 1+1 = 2；
• s：偏移位= 0+1 = 1；
• 其他 = 4+1 = 5；

举例

• haystack: haystack
• needle: sta

偏移表：

• s：偏移位= 2+1 = 3；
• t：偏移位= 1+1 = 2；
• a：偏移位= 0+1 = 1；
• 其他 = 3+1 = 5；

1. haystack
   sta
   看s是sta里面的字母，加上s的偏移位3，转到
2. haystack
   000sta
   OK!
3. return 3；

实现

BM算法

实现