algo/di-yi-zhan-da78c/shou-ba-sh-48c1d/hua-dong-c-88113/

[giscus[bot]]

algo/di-yi-zhan-da78c/shou-ba-sh-48c1d/hua-dong-c-88113/

Info 数据结构精品课 (https://aep.h5.xeknow.com/s/1XJHEO) 和 递归算法专题课 (https://aep.xet.tech/s/3YGcq3) 限时附赠网站会员！ 读完本文，你不仅学会了算法套路，还可以顺便解决如下题目： LeetCode 力扣 难度 :----: :----: :----: 187. Repea...

https://labuladong.gitee.io/algo/di-yi-zhan-da78c/shou-ba-sh-48c1d/hua-dong-c-88113/

[ccfuncy]

感觉最后的字符串匹配取模的算法有问题。用例rll,ll一直过不了

#include<bits/stdc++.h>
using namespace std;
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public:
    int strStr(string haystack, string needle) {
        int left=0,right=0;
        long Q = 1658598167;
        long R=26,L=needle.size(),windowsHash=0;
        long targetHash=0;
        int RL=1;
        for (int i = 0; i < L ; ++i) {
            RL=(RL*R)%Q;
        }
        for (int i = 0; i < needle.size(); ++i) targetHash=(targetHash*R+needle.at(i))%Q;
        while (right < haystack.size()){
            windowsHash=((windowsHash*R)%Q+haystack.at(right))%Q;
            right++;
            if (right-left==L){
                cout << targetHash  <<endl;
                if(windowsHash==targetHash){
                    if (haystack.substr(left,right-left)==needle) return left;
                }
                windowsHash=(windowsHash-(haystack.at(left)*RL)%Q+Q)%Q;
                ++left;
            }
        }
        return -1;
    }
};
//leetcode submit region end(Prohibit modification and deletion)

[NCUCyy]

计算RL的for循环多了一次

for (int i = 0; i < L ; ++i) {
    RL=(RL*R)%Q;
}
改为
```c++
for (int i = 1; i < L ; ++i) {
    RL=(RL*R)%Q;
}
就可以了。
因为RL应该是R^(L-1)
你的for循环多✖️了一个R