一维、二维Hash算法(转载 && 代码加注释版)

朱雀 2022-12-28 12:45 169阅读 0赞

### 文章目录 ###

*  一维字符串哈希
 *  二维矩阵哈希
 *  应用题目

--------------------

# 一维字符串哈希 #

**功能：在O(1)时间内查询某个区间的子串是什么(该串的哈希值)等等**

**实现方法：类似于前缀合，对字符串从前到后进行哈希**

//初始化辅助数组p
    void init()
    {
        
        p[0] = 1;
        for(int i = 1; i <= len; i ++) {
        
            p[i] = p[i-1]*base;
        }
    }
    //初始化辅助数组p
    
    //Hash变换
    void Hash()
    {
        
        has[0] = 0;
        for(int i = 1; i <= len; i ++) {
        
         	 	//这个操作类似于将字符串的每一个位置转换成base进制
            has[i] = has[i-1]*base + str[i];		//Hash表
        }
    }
    //Hash变换

**查询：查询区间\[l, r\]内字串的哈希值，has\[r\] - has\[l-1\]\*p\[r-l+1\]**

uLL get_has(int l, int r)
    {
        
      	//将l-1位置的Hash值，偏移到与r同阶，可以求出中间新增的Hash值
        return has[r] - has[l-1]*p[r-l+1];
    }

**实现代码：（查询字符串str中s出现的次数）= kmp**

const uLL base = 131;
    uLL has[100010], p[100010]; //unsigned long long 自动溢出(取模)
    char str[100010], s[100010];
    int len;
     
    //初始化辅助数组p
    void init()
    {
        
        p[0] = 1;
        for(int i = 1; i <= len; i ++) {
        
            p[i] = p[i-1]*base;
        }
    }
    //初始化辅助数组p
    
    //Hash变换
    void Hash()
    {
        
        has[0] = 0;
        for(int i = 1; i <= len; i ++) {
        
         	 	//这个操作类似于将字符串的每一个位置转换成base进制
            has[i] = has[i-1]*base + str[i];	
        }
    }
    //Hash变换
     
    uLL get_has(int l, int r)
    {
        
      	//将l-1位置的Hash值，偏移到与r同阶，可以求出中间新增的Hash值
        return has[r] - has[l-1]*p[r-l+1];
    }
     
    int main()
    {
        
        init();
        scanf("%s%s", s+1, str+1);
        int len1 = strlen(s+1);
        int len2 = strlen(str+1);
        len = len2;
      
        Hash();
      
        uLL hs = 0;
        for(int i = 1; i <= len1; i ++) {
        
            hs = hs*base + s[i];
        }
      	
      	//查询字符串str中s出现的次数
        int cnt = 0;
        for(int i = 1; i <= len2-len1+1; i ++) {
        
            if(hs == get_has(i, i+len1-1)) cnt ++;
        }
        printf("%d\n", cnt);
    }

--------------------

# 二维矩阵哈希 #

**功能：O(1)时间内查询某个子矩阵的是什么(该矩阵的哈希值)**

**实现方法：类似于二维前缀合，先对每一列进行哈希，然后再对每一行进行哈希**

const uLL base1 = 131;
    const uLL base2 = 233;
     
    int n, m;
    char mp[510][510];	//二维矩阵
    uLL has[510][510];	//Hash表
    uLL p1[510], p2[510];	//p1用于辅助 列 的Hash值，p2用与辅助 行 的Hash值
     
    //初始化辅助数组p1,p2
    void init()
    {
        
        p1[0] = p2[0] = 1;
        for(int i = 1; i <= 505; i ++) {
        
            p1[i] = p1[i-1]*base1;
            p2[i] = p2[i-1]*base2;
        }
    }
    //初始化辅助数组p1,p2
     
    //Hash变换
    void Hash()
    {
        
        has[0][0] = 0;
        has[0][1] = 0;
        has[1][0] = 0;
      
        for(int i = 1; i <= n; i ++) {
         //对列进行Hash
            for(int j = 1; j <= m; j ++) {
        
                has[i][j] = has[i][j - 1] * base1 + mp[i][j] - 'a';
            }
        }
      	
      	//在对列进行Hash之后，将列的值作为矩阵值，再次Hash
        for(int i = 1; i <= n; i++) {
        
            for(int j = 1; j <= m; j ++) {
         //对行进行Hash
                has[i][j] = has[i - 1][j] * base2 + has[i][j];
            }
        }
    }
    //Hash变换

**查询：查询某个x\*y的子矩阵(相同方法先处理出hs\[x\]\[y\]的值)在原矩阵中出现了多少次**

int check(int x , int y)
    {
        
        int cnt = 0;
        for(int i = x; i <= n; i ++) {
        
            for(int j = y; j <= m; j ++) {
        
                uLL k = has[i][j] - has[i-x][j]*p2[x] - has[i][j-y]*p1[y] + has[i-x][j-y]*p1[y]*p2[x];	
              	//加上has[i-x][j-y]*p1[y]*p2[x]的原因：
              	//因为has[i-x][j]*p2[x]和has[i][j-y]*p1[y]都是由has[i-x][j-y]*p1[y]*p2[x]变换而来
              	//因此在➖时，减去了两个has[i-x][j-y]*p1[y]*p2[x]
                if(k == hs[nn][mm]) //子矩阵的值为hs[nn][mm]
                  cnt ++;
            }
        }
        return cnt;
    }

# 应用题目 #

[应用题目 牛客练习赛1-A-矩阵 二分+ 二维Hash][_1-A-_ _ _Hash]

--------------------

*  转载于https://blog.csdn.net/I\_believe\_CWJ/article/details/82965434
 *  如若侵权，请联系删除

[_1-A-_ _ _Hash]: http://codeblog-cy.top/2020/02/18/nowcoder-prac-1-A-matrix/