字符串回文hash 模板题 O(1)判字符串是否回文

推荐： https://segmentfault.com/a/1190000021665249

板子题：判断回文串

双hash，单hash也能过
我实在不明白它和后面那个用数组存的有什么区别，m改这个一直wa
贴个别人过了的代码，等我补！
自然溢出翻车了，搞了个模数
单hash：

#include<iostream>
using namespace std;
#define ull unsigned long long
const int maxn = 1e6 + 5;
ull p = 13331;
const int mod = 1e9 + 7;
int main(){
    
    int len;
    while(cin >> len){
    
        ull hash_a = 0, hash_b = 0;
        getchar();
        int mid = len / 2;
        for (int i = 1; i <= mid; ++i){
    
            char t = getchar();
            hash_a = (hash_a * p + (ull)t) % mod;
        }
        if(len & 1)
            getchar();
        ull pp = 1;
        for (int i = 1; i <= mid; ++i){
    
            char t = getchar();
            hash_b = (hash_b + (ull)t * pp) % mod;
            pp = p * pp % mod;
        }
        if(hash_a == hash_b)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}

双hash：
对两个不同的素数取模

#include<iostream>
using namespace std;

#define ull unsigned long long
const int maxn = 1e6 + 5;
ull p = 13331;
const int mod = 1e9 + 7;
const int mod1 = 1e8 + 15;
int main(){
    
    int len;
    while(cin >> len){
    
        ull hash_a = 0, hash_b = 0,hash_aa = 0, hash_bb = 0;
        getchar();
        int mid = len / 2;
        for (int i = 1; i <= mid; ++i){
    
            char t = getchar();
            hash_a = (hash_a * p + (ull)t) % mod;
            hash_aa = (hash_aa * p + (ull)t) % mod1;
        }
        if(len & 1)
            getchar();
        ull pp = 1, pp1 = 1;
        for (int i = 1; i <= mid; ++i){
    
            char t = getchar();
            hash_b = (hash_b + (ull)t * pp) % mod;
            hash_bb = (hash_bb + (ull)t * pp1) % mod1;

            pp = p * pp % mod;
            pp1 = p * pp1 % mod1;
        }
        if(hash_a == hash_b && hash_aa == hash_bb)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}

M形字符串

M字符串定义：一个字符串是回文，它的一半也是回文

#include<iostream>
using namespace std;
#define ull unsigned long long
const int maxn = 1e6 + 5;
ull p = 13331;
ull hash_a[maxn], hash_b[maxn], power[maxn];

void init(string s, int len){
    
    hash_a[0] = 0, hash_b[0] = 0, power[0] = 1;
    for (int i = 1; i <= len; ++i){
    
        hash_a[i] = hash_a[i - 1] * p + (s[i] - 'a');
        hash_b[i] = hash_b[i - 1] * p + (s[len - i + 1] - 'a');
        power[i] = power[i - 1] * p;
    }
}

bool part_judge(int l, int r, int len){
    
    ull ta = hash_a[r] - hash_a[l - 1] * power[r - l + 1];
    ull tb = hash_b[len - l + 1] - hash_b[len - r] * power[r - l + 1];
    return ta == tb;
}

int main(){
    
    string s;
    cin >> s;
    s = " " + s;
    int len = s.size();
    int ans = 0;
    init(s, len);
    for (int i = 1; i <= len; ++i){
    
        if(part_judge(1, i, len) && part_judge(1, (i + 1) / 2, len))//分割成一半的时候，5 + 1 >> 2 == 3 4 + 1 >> 2 == 2不会影响结果
            ++ans;
    }
    cout << ans << endl;
    return 0;
}

P3501 [POI2010]ANT-Antisymmetry

题解：https://www.cnblogs.com/henry-1202/p/10321013.html

#include<iostream>
using namespace std;

#define ull unsigned long long
#define ll long long
const int maxn = 1e6 + 5;
ull p = 13331;
ull hash_a[maxn], hash_b[maxn], power[maxn], hash_aa[maxn], hash_bb[maxn], powerr[maxn];

void init(string s, int len){
    
    hash_a[0] = 0, hash_b[len + 1] = 0, power[0] = 1;
    for (int i = 1; i <= len; ++i){
    
        hash_a[i] = hash_a[i - 1] * p + (ull)(s[i]);
       // hash_b[len - i + 1] = hash_b[len - i + 2] * p + (s[len - i + 1] == '0' ? '1' : '0');
        power[i] = power[i - 1] * p;
    }
    for (int i = len; i ; --i){
    
        hash_b[i] = hash_b[i + 1] * p + (ull)(s[i] == '0' ? s[i] + 1 : s[i] - 1);
    }
}

ull part_judge1(int l, int r, int len){
    
    ull ta = hash_a[r] - hash_a[l - 1] * power[r - l + 1];
    return ta;
}

ull part_judge2(int l, int r, int len){
    
    ull tb = hash_b[l] - hash_b[r + 1] * power[r - l + 1];
    return tb;
}

ll judge(int st, int len){
    
    int l = 1, r = st;
    while(l <= r){
    
        int mid = (l + r) >> 1;
        if(part_judge1(st - mid + 1, st, len) == part_judge2(st + 1, st + mid, len))
            l = mid + 1;
        else
            r = mid - 1;
    }
    return r;
}

int main(){
    
    int len;
    cin >> len;
    string s;
    cin >> s;
    s = " " + s;
    ll ans = 0;
    init(s, len);
    for (int i = 1; i < len; ++i){
    
        ans += judge(i, len);
    }
    cout << ans << endl;
    return 0;
}