欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页  >  IT编程

字符串哈希模板+例题

程序员文章站 2022-06-25 16:15:59
模板核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果typedef unsigned long long ULL;ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64// 初始化p[0] = 1;for (int i = 1; i <= n; i ++ ){ h[i] =...

模板

核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果

typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64

// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
    h[i] = h[i - 1] * P + str[i];
    p[i] = p[i - 1] * P;
}

// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

兔子与兔子

题目描述

很久很久以前，森林里住着一群兔子。
有一天，兔子们想要研究自己的 DNA 序列。
我们首先选取一个好长好长的 DNA 序列（小兔子是外星生物，DNA 序列可能包含 26 个小写英文字母）。
然后我们每次选择两个区间，询问如果用两个区间里的 DNA 序列分别生产出来两只兔子，这两个兔子是否一模一样。
注意两个兔子一模一样只可能是他们的 DNA 序列一模一样。
输入格式
第一行输入一个 DNA 字符串 S。
第二行一个数字 m，表示 m 次询问。
接下来 m 行，每行四个数字 l1,r1,l2,r2，分别表示此次询问的两个区间，注意字符串的位置从1开始编号。
输出格式
对于每次询问，输出一行表示结果。
如果两只兔子完全相同输出 Yes，否则输出 No（注意大小写）。
数据范围
1≤length(S),m≤1000000
输入样例：
aabbaabb
3
1 3 5 7
1 3 6 8
1 2 1 2
输出样例：
Yes
No
Yes

题解

模板题，套用上面的模板即可

代码

#include <iostream>
#include <cstring>

using namespace std;

typedef unsigned long long ULL;
const int N = 1000010, base = 131;
int h[N], p[N];
char str[N];

int get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main()
{
    scanf("%s", str + 1);
    int n = strlen(str + 1);
    p[0] = 1;
    for(int i = 1; i <= n; i++)
    {
        h[i] = h[i - 1] * base + str[i] - 'a' + 1;
        p[i] = p[i - 1] * base;
    }
    
    int m;
    scanf("%d", &m);
    while(m--)
    {
        int l1, r1, l2, r2;
        scanf("%d%d%d%d" , &l1, &r1, &l2, &r2);
        if(get(l1, r1) == get(l2, r2)) puts("Yes");
        else puts("No");
    }
    
    return 0;
}

回文子串的最大长度

题目描述

如果一个字符串正着读和倒着读是一样的，则称它是回文的。
给定一个长度为N的字符串S，求他的最长回文子串的长度是多少。
输入格式
输入将包含最多30个测试用例，每个测试用例占一行，以最多1000000个小写字符的形式给出。
输入以一个以字符串“END”（不包括引号）开头的行表示输入终止。
输出格式
对于输入中的每个测试用例，输出测试用例编号和最大回文子串的长度（参考样例格式）。
每个输出占一行。
输入样例：
abcbabcbabcba
abacacbaaaab
END
输出样例：
Case 1: 13
Case 2: 6

题解

  1. 套用字符串哈希算法。算出正序，逆序哈希。
  2. 枚举中点，然后二分半径。
  3. 技巧：在字符之间插入一个#，这样字符串长度就变成了偶数，但要注意的是：算原来字符长度的时候
    要判断第一个字符是什么，如果不是#，这样字符长度就是半径+1，否则就是半径。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef unsigned long long ULL;
const int N = 2000010, base = 131;
char str[N];
ULL hl[N], hr[N], p[N];

ULL get(ULL h[], int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main()
{
    
    int T = 1;
    
    while(scanf("%s", str + 1), strcmp(str + 1, "END"))
    {
        int n = strlen(str + 1);
        
        for(int i = 2 * n; i ; i -= 2) //在字符之间插入一个其他字符
        {
            str[i] = str[i / 2];
            str[i - 1] = 'a' + 26;
        }
        
        n = n * 2; //注意要更新n
        
        p[0] = 1;
        
        for(int i = 1, j = n; i <= n; i++, j--)
        {
            hl[i] = hl[i - 1] * base + str[i] -'a' + 1;
            hr[i] = hr[i - 1] * base + str[j] -'a' + 1;
            p[i] = p[i - 1] * base;
        }
        
        int res = 0;
        
        for(int i = 1; i <= n; i++) //枚举中点
        {
            int l = 0, r = min(i - 1, n - i);
            while(l < r) //二分半径
            {
                int mid = l + r + 1 >> 1;
                //算hr[]的时候要注意下标对应
                if(get(hl, i - mid, i - 1) != get(hr, n - (i + mid) + 1, n - (i + 1) + 1)) r = mid - 1;
                else l = mid;
            }
            
            if(str[i - l] <= 'z') res = max(res, l + 1);
            else res = max(res, l);
        }
        
        printf("Case %d: %d\n", T++, res);
    }
    
    
    return 0;
}

后缀数组

题目描述

后缀数组 (SA) 是一种重要的数据结构，通常使用倍增或者DC3算法实现，这超出了我们的讨论范围。
在本题中，我们希望使用快排、Hash与二分实现一个简单的O(nlog2n)的后缀数组求法。
详细地说，给定一个长度为 n 的字符串S（下标 0~n-1），我们可以用整数 k(0≤k<n) 表示字符串S的后缀 S(k~n-1)。
把字符串S的所有后缀按照字典序排列，排名为 i 的后缀记为 SA[i]。
额外地，我们考虑排名为 i 的后缀与排名为 i-1 的后缀，把二者的最长公共前缀的长度记为 Height[i]。
我们的任务就是求出SA与Height这两个数组。
输入格式
输入一个字符串，其长度不超过30万。
字符串由小写字母构成。
输出格式
第一行为数组SA，相邻两个整数用1个空格隔开。
第二行为数组Height，相邻两个整数用1个空格隔开，我们规定Height[1]=0。
输入样例：
ponoiiipoi
输出样例：
9 4 5 6 2 8 3 1 7 0
0 1 2 1 0 0 2 1 0 2

题解

  1. 先想出朴素做法：用一个下标表示字符串后缀的开头。然后使用快排对这些后缀排序。
    比较函数：挨个字符比较。
  2. 求两个字符串的最长公共前缀长度，可以用字符串哈希的做法。即二分枚举最大长度，如何判断
    这两个字符串是相同的呢？可以求出在这个长度下的字符串哈希值，通过比较哈希值，判断在这两个字符串是不是相同的字符串。
  3. 优化比较函数：可以先求出两个后缀的最大公共长度，然后比较最大公共长度后一个字符的大小即可。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <limits.h>

using namespace std;
typedef unsigned long long ULL;
const int N = 300010, base = 131;
char str[N];
int sa[N];
ULL h[N], p[N];
int n;

ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

//二分获取最大公共长度
int get_max_common_prefix(int a, int b)
{
    int l = 0, r = min(n - a + 1, n - b + 1);
    while(l < r)
    {
        int mid = l + r + 1>> 1;
        if(get(a, a + mid - 1) != get(b, b + mid - 1)) r = mid - 1;
        else l = mid;
    }
    
    return l;
}

//比较函数
bool cmp(int a, int b)
{
    int l = get_max_common_prefix(a, b);
    int av = str[a + l];
    int bv = str[b + l];
    return av < bv;
}

int main()
{
    scanf("%s", str + 1);
    
    n = strlen(str + 1);
    
    p[0] = 1;
    for(int i = 1; i <= n; i++)
    {
        h[i] = h[i - 1] * base + str[i] - 'a' + 1;
        p[i] = p[i - 1] * base;
        sa[i] = i;
    }
    
    sort(sa + 1, sa + n + 1, cmp); //排索引
    
    for(int i = 1; i <= n; i++) printf("%d ", sa[i] - 1);
    puts("");
    for(int i = 1; i <= n; i++)
    {
        if(i == 1) printf("0 ");
        else printf("%d ", get_max_common_prefix(sa[i - 1], sa[i]));
    }
    
    puts(" ");
    
    return 0;
}

本文地址：https://blog.csdn.net/xiaoxiongyuan__s/article/details/109229366

相关标签： 字符串 算法 哈希表 c++

上一篇： 【牛客网机试】写出一个程序，接受一个十六进制的数，输出该数值的十进制表示。

下一篇： 进程命令ps/top/kill

推荐阅读