字符串Hash

本部分只是字符串Hash的一些操作和习题的笔记

想了解其中原理和更多知识可以点击此处

Hash基数: 131

Hash大模数:1e9+7, 19260817,89999794200117649,999999786000011449,998244353

字符串Hash的应用

  • 字符串匹配

    多项式Hash处理,然后,比较两个字符串子串的Hash是否相同来判断字符串是否相等

    作为基数的base和不使用自然溢出时选取的模数非常重要,必要时选用双hash

    //base[i]表示base的i次幂
    //hash[i]表示字符串s从1到i的子串的hash值
    using ull = unsigned long long;
    //查询子串的hash值:
    	ull getHash(int left , int right){
    	hashValue = hash[right] - hash[left - 1] * base[right - left + 1];
    }
    
    //查询子串中删除去一个字符后的hash值
    ull getHashDelete(int left ,int right , int idx){
    	hashValue = getHash(left , idx - 1) * base[right - idx] + getHash(idx + 1 , rs);
    }
    
    //查询两个子串拼接的hash值
    ull getTwoSubstrHash(int lr , int rs , int x , int y){
        return gethash(lr , rs) * base[y - x + 1] + gethash(x , y);
    }
    

    习题 :

    Clairewd’s message

    P2957 [USACO09OCT]Barn Echoes G

    P3370 【模板】字符串哈希

    P5018 [NOIP2018 普及组] 对称二叉树(双Hash,非字符串)

    P1381 单词背诵

    P6739 [BalticOI 2014 Day1] Three Friends

    P4421 [COCI2017-2018#1] Lozinke

    CF1200E Compress Words

  • 允许k次失配的字符串匹配

    习题:

    P3763 [TJOI2017]DNA

  • 最长回文子串

    二分答案+ 字符串hash

    const int N = 1e6 + 5;
    ull p[N], hash1[N], hash2[N];
    const ull base = 131;//幂次
    //获得正向字符串的hash值
    ull gethash1(int lr, int rs , ull hash[]) {
    	return hash[rs] - hash[lr - 1] * p[rs - lr + 1];
    }
    //获得逆向字符串的hash值
    ull gethash2(int lr , int rs , ull hash[]){
        return hash2[lr] - hash2[rs + 1] * p[rs - lr + 1];
    }
    char s[N];
    int n;
    int res;
    int T;
    int main() {
        int cnt = 0;
        //预处理base的幂次
        p[0] = 1;
        for(int i = 1 ; i < N ; ++i) p[i] = p[i - 1] * base;
        while(true){
            res = 1;
            ++cnt;
    	    scanf("%s", s + 1);
    	    if(s[1] =='E') break;
    	    n = strlen(s + 1);
    	    //获得字符串的hash值
    	    for (int i = 1; i <= n; ++i)   hash1[i] = hash1[i - 1] * base + (s[i] - 'a' + 1);
    	    for(int i = n ; i >= 1 ;--i)   hash2[i] = hash2[i + 1] * base + (s[i] - 'a' + 1 ) ;
    	    //二分答案
    	    for(int i = 1 ; i <= n ; ++i){
    	        //二分奇回文
    	        int lr = 0 , rs = min(i - 1 , n - i);
    	        while(lr < rs){
    	            int mid = (lr + rs  + 1) >> 1;
    	            if(gethash1(i - mid , i - 1, hash1) == gethash2(i + 1, i + mid,  hash2)) lr = mid;
    	            else rs = mid - 1;
    	        }
    	        chkmax(res , lr * 2 + 1);
    	        //二分偶回文
    	        lr = 0 ; rs = min(i , n - i);
    	        while(lr < rs){
    	            int mid = (lr + rs + 1) >> 1;
    	            if(gethash1(i - mid + 1 , i , hash1) == gethash2(i + 1, i + mid,  hash2)) lr = mid;
    	            else rs = mid - 1;
    	        }
    	        chkmax(res , lr * 2);
    	    }
    	    printf("Case %d: %d\n",cnt , res);
        }
    	return 0;
    }
    

    习题:

    P3501 [POI2010]ANT-Antisymmetry

    139. 回文子串的最大长度

    最长回文

    CF7D Palindrome Degree

上一篇:uni.uploadFile() 成功后返回数据为JSON.stringify()


下一篇:.NET架构小技巧(8)——优待异常