洛必达法则(字符串哈希)

发表于 更新于

一、算法模板

参考 OI Wiki： https://oi-wiki.org/string/hash/

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
const int maxn = 2010;
int prefix_hash[maxn];
int suffix_hash[maxn];
int base_power[maxn];
const int M = 1e9 + 7;
const int B = 233;
using ll = long long;

void init_hash(string &str, int n){
    for(int i = 0, val = 1; i < maxn; ++i){
        base_power[i] = val, val = ((ll)val * B) % M;
    }
    for(int i = 0, val = 0; i < n; ++i){
        prefix_hash[i] = val = ((ll)val * B + str[i]) % M;
    }
    for(int i = n-1, val = 0; i >=0; --i){
        suffix_hash[i] = val = ((ll)val * B + str[i]) % M;
    }
}
int segment_prefix_hash(int i, int j){
    int ans = prefix_hash[j];
    if(i != 0) ans = (ans - (ll)prefix_hash[i - 1] * base_power[j-i+1]) % M;
    if(ans < 0) ans += M;
    return ans;
}
int segment_suffix_hash(int i, int j, int n){
    int ans = suffix_hash[i];
    if(j != n-1) ans = (ans - (ll)suffix_hash[j + 1] * base_power[j-i+1]) % M;
    if(ans < 0) ans += M;
    return ans;
}

bool is_palindrome(int i, int j, int n){
    return segment_prefix_hash(i, j) == segment_suffix_hash(i, j, n);
}

二、最长回文串

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
58
59
60
61
62
63
64
65
// https://leetcode.cn/problems/longest-palindromic-substring/submissions/468447762/
// hash相等的时候需要判断一次，这里没做也能过
const int maxn = 1010;
int PHash[maxn];
int SHash[maxn];
int BP[maxn];
const int M = 1e9 + 7;
const int B = 233;
typedef long long ll;

void initHash(string &str, int n){
    for(int i = 0, val = 1; i < maxn; ++i){
        BP[i] = val, val = ((ll)val * B) % M;
    }
    for(int i = 0, val = 0; i < n; ++i){
        PHash[i] = val = ((ll)val * B + str[i]) % M;
    }
    for(int i = n-1, val = 0; i >=0; --i){
        SHash[i] = val = ((ll)val * B + str[i]) % M;
    }
}
int segPHash(int i, int j){
    int ans = PHash[j];
    if(i != 0) ans = (ans - (ll)PHash[i - 1] * BP[j-i+1]) % M;
    if(ans < 0) ans += M; 
    return ans;
}
int segSHash(int i, int j, int n){
    int ans = SHash[i];
    if(j != n-1) ans = (ans - (ll)SHash[j + 1] * BP[j-i+1]) % M;
    if(ans < 0) ans += M; 
    return ans;
}

class Solution {
public:
    string longestPalindrome(string& s) {

        if(!s.size()) return s;
        int n = s.size(), maxLen = 1, pos = 0, lastLen = 1;
        initHash(s, n);
        //cout << segPHash(0,0) << endl;
        //cout << segPHash(1,1) << endl;
        //cout << segSHash(1,1,n) << endl;
        for(int i = 1; i < n; ++i){
            //最大回文长度
            int k = min(i + 1, lastLen + 2);
            lastLen = 1;
            while(k>1){
                // 回文半径长度
                int len = (k >> 1) + (k & 1);
                int lh = segPHash(i-k+1, i-k+len);
                int rh = segSHash(i-len+1, i,n);
                //printf(" %d %d %d %d %d %d =>>>>>>>>      ", i-k+1, i-k+len, i-len+1, i, lh,rh);
                //cout << s.substr(i-k+1, len) << " : " << s.substr(i-len+1, len) << endl;
                if(lh == rh){
                    if(k > maxLen) maxLen = k, pos = i;
                    lastLen = k;break;
                }
                --k;
            }
        }
        return s.substr(pos-maxLen+1,maxLen);
    }
};