滑动窗口算法延伸：Rabin Karp 字符匹配算法 :: labuladong的算法小抄

[utterances-bot]

滑动窗口算法延伸：Rabin Karp 字符匹配算法 :: labuladong的算法小抄

https://labuladong.github.io/algo/2/19/27/

[Maxiah]

好难啊啊😭

[Yjppj]

纯纯滑动窗口思路Java代码如下：

  public static List<String> findRepeatedDnaSequences(String s) {
       int L = 10;
       Set<String> res = new HashSet();
       List<String> Fres = new ArrayList<>();
       HashSet<String> seen = new HashSet<>();

       List<Character> window = new ArrayList<>();
       int left = 0;int right = 0;
       while (right < s.length()) {
           window.add(s.charAt(right));
           right++;
           if (right - left == L) {
               String windowStr = "";

               for (int i = 0 ; i < window.size();i++) {
                   windowStr += window.get(i);
               }


               if (seen.contains(windowStr)) {
//                   System.out.println("找到一个重复子串: "+ windowStr);
                   res.add(windowStr);
               }else {
                   seen.add(windowStr);
               }
               window.remove(0);
               left++;
           }
       }
       Fres.addAll(res);
    return Fres;
    }

[Geeksun2018]

window用LinkedList是不是更合适一些呀？

[bruceeewong]

我认为这里不需要实际的window，left，right两个游标就相当于window了；windowStr那里换成s.substring(left, right) 取就好了

[Jlif]

func findRepeatedDnaSequences(s string) []string {
	arr := make([]byte, len(s))
	for i, v := range s {
		switch string(v) {
		case "A":
			arr[i] = 0
		case "C":
			arr[i] = 1
		case "G":
			arr[i] = 2
		case "T":
			arr[i] = 3
		}
	}

	left, right := 0, 0
	var res []string
	resMap := map[string]struct{}{}
	seek := map[int]bool{}

	tmp := 0
	for right < len(arr) {
		tmp = addNewStr(tmp, arr[right])
		right++

		for right-left >= 10 {
			if _, exist := seek[tmp]; exist {
				resMap[s[left:right]] = struct{}{}
			} else {
				seek[tmp] = true
			}
			left++
		}
	}

	for key := range resMap {
		res = append(res, key)
	}

	return res
}

func addNewStr(num int, b byte) int {
	num = num << 2
	num = num & 0xfffff
	num = num | int(b)
	return num
}

go语言解决重复的DNA序列问题，感谢大佬提供的思路

[Jlif]

取了个巧，刚好这个问题只需要求重复的10个序列，而总共只有4种碱基，利用2个bit位刚好能够表示，总共只需要20个bit位，也就是int32其实就够了

[zhaoedf]

我看官方题解下面也有人在讨论DNA这个题，如本书作者所说(下图1)，O(L)的时间复杂度来自于生成子串，可是加入了hash后还是存在生成子串的过程吧(下图2)？所以时间复杂度不是应该还是要考虑L？

[guqihao-7]

我觉得应该是摊还(平均)时间复杂度是O(N)。算法时空复杂度分析指南 一文中提到过这个概念，其中有一段话是这样的：

想想之前说的数据结构扩容的场景，也许 N 次操作中的某一次操作恰好触发了扩容，导致时间复杂度提高，但不可能每次操作都触发扩容吧？所以总的时间复杂度依然保持在 O(N)，均摊到每一次操作上，其平均时间复杂度依然是 O(1)。

我觉得这里应该也是因为不是每次操作都会截取字符串，所以时间复杂度均摊到每次操作上仍然是O(N)。而在O(NL)版的代码中：

for (int i = 0; i + 10 <= n; i++) {
        String subStr = s.substring(i, i + 10);
        if (seen.contains(subStr)){
            // 之前出现过，找到一个重复的
            res.add(subStr);
        } else {
            // 之前没出现过，加入集合
            seen.add(subStr);
        }
    }

每次操作一定会截取字符串，所以时间复杂度是O(NL)

[labuladong]

这个解法应该没啥可说的啊，只要有 substring 的操作，肯定是 O(NL)。除非你用最后的 Rabin Karp 算法，时间复杂度才能降到 O(N)。

[labuladong]

好吧，我之前没太看懂大家的疑惑的点，感谢 @guqihao-7 私信跟我探讨，我明白大家在讨论什么了。

确实，如果说极端情况（比如全是重复的字符），每个字符都会触发 substring 操作，这种情况下复杂度确实降到 O(NL) 了。这就好比快速排序，我们说快排的理论时间复杂度是 O(NlogN)，但极端情况会退化成 O(N^2)，类似的道理。

所以比较完整的解释应该如 @guqihao-7 所说的，正常情况下平均时间复杂度是 O(N)，但极端情况下可能降到 O(NL)。这个细节文中确实略过了，我更新一下。

[fantian007]

TypeScript

function findRepeatedDnaSequences(s: string): string[] {
  const ret: Set<string> = new Set();

  const n = s.length;

  const map = {
    'A': 0,
    'G': 1,
    'C': 2,
    'T': 3,
  };

  const nums: number[] = new Array(n);

  // 将字符串转数字
  for(let i = 0; i < n; i++) {
    nums[i] = map[s[i]];
  };


  // 数字长度
  const L = 10;
  // 4 进制
  const R = 4;
  const RL = Math.pow(R, L - 1);

  // 左右窗口边界索引
  let left = 0;
  let right = 0;

  // 记录重复出现的 hash 值
  const seenHash = {};

  // 窗口内 hash
  let windowHash = 0;

  while (right < s.length) {
    windowHash = windowHash * R + nums[right];

    right++;

    while (right - left === L) {
      if (seenHash[windowHash]) {
        ret.add(s.substring(left, right));
      } else {
        seenHash[windowHash] = true;
      }

      windowHash = windowHash - nums[left] * RL;

      left++;
    }
  }

  return Array.from(ret);
};

[LeeHaruYa]

滴滴滴打卡

[lhcezx]

第一章早就刷完了怎么还没小旗子，原来更新了

[Goolloo]

推导一下公式

hashBase = 1658598167
needleHashBase = hashStep ^ (needle.length - 1)
hash = hash - charToRemove * needleHashBase
     => (hash - charToRemove * needleHashBase) % hashBase      // this is not equivalent, will cause hash collision
     = ((hash - charToRemove * needleHashBase) + hashBase) % hashBase      // (a) % Q = (a + Q) % Q, in case for negative when removing a char
     = ((hash % hashBase - charToRemove * needleHashBase % hashBase) + hashBase) % hashBase     // (a + b) % Q = (a % Q + b % Q) % Q, mod each one to prevent overflow
     = ((hash - charToRemove * needleHashBase % hashBase) + hashBase) % hashBase     // hash was alread moded by hashBase in the previous step, so hash % hashBase = hash

[l2009312042]

-1%3 =2 最后rabin-karp算法中的左移处理时，不加Q也是可以的

[yonggui-yan]

打卡
为了避免整型溢出，选一个大素数Q，取模。

[hongyu-yan1998]

windowHash = ((R * windowHash) % Q + txt.charAt(right)) % Q
为什么不是 windowHash = (R * windowHash+ txt.charAt(right)) % Q
或者 windowHash = ((R * windowHash) % Q + txt.charAt(right) % Q ) % Q 呢

[labuladong]

都是一样的，但只有第一种和第三种写法能避免整型溢出

[hongyu-yan1998]

原来如此，谢谢！我看到文章中的运算法则是 (X + Y) % Q == (X % Q + Y % Q) % Q ，还以为只有这两种写法

[labuladong]

嗯，R * windowHash 会很大，所以必须 %Q，txt.charAt(right) 很小，所以没必要 %Q。

[hongyu-yan1998]

懂了！谢谢

[codezcq]

class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        int [] nums = new int [s.length()];
        for(int i = 0 ; i<s.length();i++){
            switch(s.charAt(i)){
                case 'A':{nums[i]=0; break;}
                case 'C':{nums[i]=1; break;}
                case 'G':{nums[i]=2; break;}
                case 'T':{nums[i]=3; break;}
            }
        } 
        int L = 10 , R = 4, RL = (int)Math.pow(R,L-1);
        HashSet<Integer> seen = new HashSet<>();
        int window = 0;
        HashSet<String> res = new HashSet<>();
        int left = 0 , right = 0;
        while(right < nums.length){
            window = R * window + nums[right];
            right++;
            while(right-left == L){
                if(seen.contains(window)){
                    res.add(s.substring(left,right));
                }else{
                    seen.add(window);
                }
                window = window - nums[left]*RL;
                left++;
            }
        }
        return new ArrayList<String>(res);
    }
   
}

[yinmaoning55]

字符串太长 超过long上限了。。。。

[yinmaoning55]

text bbabbaaaababaaaababaaabbaabaabaabaababbaaabbbabbaaaabbbbaabbbababbbabababaaabaaa
测试用例 {"aaabaaabaaaa","abbbbbbabbaba","aaababaaa","abaabbbb","aaaabbbaababba"}
public static int[][] indexPairs(String text, String[] words) {

    List<List<Integer>> list = new ArrayList<>();
    int R = 256;
    for(int i = 0; i < words.length; i++){
        String s = words[i];
        int L = s.length();
        Long RL = (long)Math.pow(R,L-1);
        int left = 0, right = 0;
        long windowHash = 0;
        long SHash = 0;
        for(int j = 0; j < L; j++){
            SHash = SHash * R + s.charAt(j);
        }
        while(right < text.length()){
            windowHash = windowHash * R + text.charAt(right);
            right++;
            if(right - left == L){
                System.out.println(windowHash+"-------"+SHash);
                if(windowHash == SHash){
                    List<Integer> l = new ArrayList<>();
                    l.add(left);
                    l.add((right - 1));
                    list.add(l);
                }
                windowHash = windowHash - RL * text.charAt(left);
                left ++;
            }
        }
    }
    int[][] array = new int[list.size()][2];
    for (int i = 0; i < list.size(); i++) {
        array[i][0] = list.get(i).get(0);
        array[i][1] = list.get(i).get(1);
    }
    Arrays.sort(array, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0]);
    return array;

结果是超过long上限了

[BailingZhann]

一刷 看到这部分打算暂时跳过了😭

[Jacob773]

总结一下知识，并且提出一个问题：

There are two important properties of modulo:
``(a + b) mod n = [(a mod n) + (b mod n)] mod n ab mod n = [(a mod n)(b mod n)] mod n`

1. 如果不考虑溢出的问题

扩大窗口

hash_value = hash_value * R + right_digit

缩小窗口

hash_value = hash_value - left_digit * R**(L-1)

2. 如果考虑防止溢出问题

扩大窗口

hash_value % Q = (hash_value * R + right_digit) % Q

缩小窗口

hash_value % Q = (hash_value - left_digit * R**(L-1)) % Q
= ( hash_value % Q - (left_digit * (R ** (L-1)) % Q ) % Q

计算这部分
(left_digit * (R ** (L - 1) ) ) % Q
= (left_digit % Q * (R**(L-1)) % Q ) % Q

这部分
(R**(L-1)) % Q
如何计算呢？
试着用mod的 property ab mod n 推导

R ** (L - 1) = R * R * R ... * R

= R ** (L - 1) % Q = (R * R * R ... * R) % Q

= (R % Q * R^(L - 2) % Q) % Q

  = (R % Q * (R % Q * R^(L - 3) % Q) % Q ） % Q

If L = 3
R ** 2 % Q
= (R % Q * R % Q) % Q

用计算文中RL的方法：

RL = 1
for i in [1, 2]:
	RL = (RL * R) % Q

( ( R % Q) * R) % Q
== (R % Q * R % Q) % Q ??
为什么这个是对的呢？

[yusun97]

因为int R = 256很小 而long Q = 1658598167很大
256%1658598167 = 256, R%Q = R

[bruceeewong]

20230107 打卡，并提出一个灵魂问题：如果自己面试裸写，是不是还要写一个求素数的逻辑，否则怎么记得住2333

[jessycalcalcal]

这个解法里的window变量是不是可以不用，毕竟子串可以通过substring(left, right)得到
int L = 10;
HashSet seen;

// 滑动窗口代码框架
CharWindow window;
int left = 0, right = 0;
while (right < s.size()) {
// 扩大窗口，移入字符
window.addRight(s[right]);
right++;

// 当子串的长度达到要求
if (right - left == L) {
    // 把窗口中的字符变成字符串，还是需要 O(L) 的时间
    String windowStr = window.toString();
    if (seen.contains(windowStr)) {
        print("找到一个重复子串: ", windowStr);
    } else {
        seen.add(windowHash);
    }

    // 缩小窗口，移出字符
    window.removeLeft();
    left++;
}

}

[xinjicong]

python 版本

class Solution:
    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        DNA_dict = {"A":0,"C":1,"G":2,"T":3}
        result = set()
        window = set()
        # window_num应该是一个十位长的四进制数，每个数位上都代表着一种核酸类型
        # 计算四进制数的十进制结果,通过保留四进制数，而不是十进制数和字符串，是为了节省内存空间
        R = 4
        L = 10
        RL = pow(4,L - 1) # 最高位
        window_num = 0
        
        n = len(s)
        if n < 10:
            return []
        else:
            # 设定初始的windows
            left = 0
            right = 9
            for i in range(10):
                DNA = s[i]
                window_num = window_num * R + DNA_dict[DNA]


        while right < n:
            # 每一次都是sub切片，所以会多次遍历s
            if window_num not in window:
                window.add(window_num)
            else:
                result.add(s[left:right+1])
            # 减去最高位
            window_num = window_num - DNA_dict[s[left]]*RL
            left += 1
            right += 1
            if right != n:
                #  向高位移动，再加上最低位
                window_num = window_num * R + DNA_dict[s[right]]
            

        return list(result)

[hurongjie123]

同用dict存储字符编码，遍历时查表

class Solution:
    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        dict_num = {'A':0,'C':1,"G":2,'T':3}
        seen = set()
        res = set()
        r = 4
        L = 10 #记录数字的位数
        RL= r**(L-1) #用于记录最高位的数字，方便滑动窗口进行缩小操作

        windowHash = 0
        
        left,right = 0,0
        while(right < len(s)):
            windowHash = dict_num[s[right]] + windowHash*r
            right += 1
            if(right- left == L):
                if windowHash in seen:
                    res.add(s[left:right])
                else:
                    seen.add(windowHash)
                windowHash -= dict_num[s[left]] *RL
                left += 1
        return list(res)  

[Sma1lboy]

woc吊

[Math-chen]

/* 在最高位删除一个数字 */
int number = 8264;
// number 的进制
int R = 10;
// number 最高位的数字
int removeVal = 8;
// 此时 number 的位数
int L = 4;
// 运算，删除最高位数字
number = number - removeVal * R^(L-1);
// 此时 number = 264

这段是否有点问题，最高位如果为0，计算的结果等于数字本身，而例子中的计算DNA那题实际是存在高位为0的情况的

[Jack-cin]

//Rabin 考不考不得知 下面这种解法适合我等菜菜

class Solution {
public:
vector findRepeatedDnaSequences(string s) {
if(s.size()<10) return {};
//
string sub=s.substr(0,10);
map<string,int> window{{sub,1}};
//window.insert({sub,1});

    vector<string> res;
    for(int i=10;i<s.size();i++){
        sub+=s[i];
        sub.erase(sub.begin());
        //与左侧窗口比较，出现1次说明重复
        if(window[sub]==1){//如果>=1的话，会出现重复添加错误,ax8b ax8b ax8b
            res.push_back(sub);
        }
        window[sub]++;
    }
    return res;
}

};

[CarlLy7]

打卡，值得二刷

[LJK314]

最后一份代码里面的for(int i = 1; i <= L - 1; i++)，要把等号去掉。

[c0sc0s]

优雅的JS代码

var findRepeatedDnaSequences = function(s) {
    if(s.length <= 10) return [];
    const set = new Set(), ans = [];;
    set.add(s.substring(0,10)); //存第一个子串
    let l = 1 , r = 10; //从第二个子串开始

    while(r<s.length){
        const str = s.substring(l++,++r);
        set.has(str) ? ans.push(str) : set.add(str);
    }
    return Array.from(new Set(ans));
};

[AlanKang98]

这真的是四分钟能读完的吗