[basic] 1. 杂项 - lmcdhr/algorithm-note-from-leetcode GitHub Wiki

整理自九章算法基础版视频

1. Rabin Karp算法

1. 使用场景：字符串查找

2. 基本思路：将字符串变成整数（按位乘M，再取模，取模是因为得出结果过大），整数的比较和查找时间复杂度是O（1），实现方法是使用hash

3. 基础题目：

4. 其他栗子：leetcode28:implement strStr()

1. 题目：给予一个source string，再给予一个target string，判断target字符串是否包含于source中（连续且按顺序），如果包含，返回source中对应target第一个char的位置，否则返回-1

example：
1.
source:hello target: ll
return: 2

2. 
source:hello target: eo
return:-1

2. 思路一：前向指针做法：time：O((m-n)*n) space:1

class Solution {
public:
    int strStr(string haystack, string needle) {
        if(needle.length()>haystack.length())
            return -1;
        if(needle.empty())
            return 0;
        if (haystack.empty())
            return -1; 
        for(int i=0;i<=haystack.length()-needle.length();i++)
        {
            int j=0;
            while(j<needle.length()&&haystack[i+j]==needle[j])
            {
                j++;
                if(j==needle.length())
                    return i;
            }
        }
        return -1;
        }
};

3. Rabin Karp:
   1. 解析：