首页 > 其他分享 >字符串哈希

字符串哈希

时间:2024-07-19 19:55:09浏览次数:18  
标签:return ull int s1 long 哈希 字符串 ll

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int, int> pii;
typedef pair<ll, ll> PII;
#define pb emplace_back
//#define int ll
#define all(a) a.begin(),a.end()
#define x first
#define y second
#define ps push_back
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)

void solve();

const int N = 1e6 + 10;
ull p1[N],p2[N],h1[N],h2[N];
ll n;
string s1,s2;
ll ls1,ls2;
const ll P = 131;
ull has1;

signed main() {
    IOS;
    ll t;
    cin >> t;
    while(t--)
    solve();
    return 0;
}

ull get1(int l,int r)
{
    if(l < 1 || l > r || r > ls1)
        return 0;
    return h1[r] - h1[l-1] * p1[r - l + 1];
}
ull get2(int l,int r)
{
    if(l < 1 || l > r || r > ls2)
        return 0;
    return h2[r] - h2[l-1] * p2[r - l + 1];
}
void solve() {
    s1.clear(),s2.clear();
    cin >> s1 >> s2;
    ll len = s1.size();
    s1 = s1 + s1;
    ls1 = s1.size(),ls2 = s2.size();
    s1 = ' ' + s1;
    s2 = ' ' + s2;
    p1[0] = p2[0] = 1;
    // s1 的 hash值
    for(int i = 1; i <= ls1; ++ i)
    {
        h1[i] = h1[i-1]*P + s1[i] - 'A';
        p1[i] = p1[i-1]*P;// 进制
    }
    // s2 的 hash值
    for(int i = 1; i <= ls2; ++ i)
    {
        h2[i] = h2[i - 1] * P + s2[i] - 'A';
        p2[i] = p2[i - 1] * P;
    }
    map<ll,ll> mp;
    for(int i = 1; i <= ls2; ++ i)
    {
        ll j = i + len - 1;
        if(j > ls2) break;
        mp[get2(i,j)] ++;
    }
    ll ans = 0;
    for(int i = 1; i <= len; ++ i)
    {
        ll j = i + len - 1;
        if(j > ls1) break;
        ans += mp[get1(i,j)];
    }
    cout << ans << endl;
}
#pragma GCC optimize("Ofast,inline,unroll-loops,fast-math,no-stack-protector")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
const int N = 1e6;
const int mod = 131;
int lt, ls;
ull p1[N], h1[N], p2[N], h2[N];

// 计算字符串t从l到r的哈希值
ull get1(int l, int r)
{
    if (l > r || l < 1 || r > lt)
        return 0;
    return h1[r] - h1[l - 1] * p1[r - l + 1];
}

// 计算字符串s从l到r的哈希值
ull get2(int l, int r)
{
    if (l > r || l < 1 || r > ls)
        return 0;
    return h2[r] - h2[l - 1] * p2[r - l + 1];
}

void solve()
{
    string t, s;
    cin >> t >> s;
    int len = t.size();
    t = t + t; // 将t复制一份拼接在原字符串后面,方便后续计算循环位移
    lt = t.size(), ls = s.size();
    t = " " + t; // 在字符串开头添加一个空格,方便计算哈希值
    s = " " + s;
    p1[0] = p2[0] = 1;
    for (int i = 1; i <= lt; i++)
    {
        h1[i] = h1[i - 1] * mod + t[i] - '0'; // 计算t的哈希值
        p1[i] = p1[i - 1] * mod; // 计算模数的幂次方
    }
    for (int i = 1; i <= ls; i++)
    {
        h2[i] = h2[i - 1] * mod + s[i] - '0'; // 计算s的哈希值
        p2[i] = p2[i - 1] * mod; // 计算模数的幂次方
    }
    map<ll, ll> mp;
    for (int i = 1; i <= ls; i++)
    {
        int j = i + len - 1;
        if (j > ls)
            break;
        mp[get2(i, j)]++; // 统计s中所有长度为len的子串的哈希值出现次数
    }
    ll ans = 0;
    for (int i = 1; i <= len; i++)
    {
        int j = i + len - 1;
        if (j > lt)
            break;
        ans += mp[get1(i, j)]; // 累加s中子串在t的循环位移版本中出现的次数
    }
    cout << ans << endl; // 输出结果
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1;
    cin >> _;
    while (_--)
        solve();
    return 0;
}

 

 

标签:return,ull,int,s1,long,哈希,字符串,ll
From: https://blog.csdn.net/2303_79552392/article/details/140552447

相关文章

  • Redis系列命令更新--Redis字符串命令
    1、RedisSET命令 (1)说明:用于设置给定key的值;如果key已经存储其他值,SET就覆写旧值,且无视类型;(2)语法:redis127.0.0.1:6379>SETKEY_NAMEVALUE(3)实例:#对不存在的键进行设置redis127.0.0.1:6379>SETkey"value"OKredis127.0.0.1:6379>GETkey"value"#对已存在的键......
  • 算法刷题笔记 字符串哈希(C++实现)
    文章目录题目描述基本思路实现代码题目描述给定一个长度为n的字符串,再给定m个询问,每个询问包含四个整数l1,r1,l2,r2,请你判断[l1,r1]和[l2,r2]这两个区间所包含的字符串子串是否完全相同。字符串中只包含大小写英文字母和数字。输入格式第一行包含整数n和m,表示字符......
  • JSON 格式的字符串反序列化为 .NET 对象
    DeserializeObject是Newtonsoft.Json(通常简称为Json.NET)库中的一个方法,用于将JSON格式的字符串反序列化为.NET对象。这个方法允许你将JSON数据转换成C#中的类实例,使得你可以方便地在程序中操作这些数据。使用方法要使用DeserializeObject方法,你首先需要安装Newton......
  • 哈希
    哈希 我认为的哈希:比较两个东西是否相同把一个东西提前映射成一个数,像map,但是O(1)比较  字符串哈希(进制哈希)   详解 https://www.luogu.com.cn/problem/P3370第1题   字符串哈希 查看测评数据信息如题,给定N个字符串(第i个字符串长度为Mi,字符串......
  • 蓝桥杯省赛 垂直柱状图(字符串+模拟)
    描述写一个程序从输入文件中去读取四行大写字母(全都是大写的,每行不超过 100 个字符),然后用柱状图输出每个字符在输入文件中出现的次数。严格地按照输出样例来安排你的输出格式。输入描述四行字符,由大写字母组成,每行不超过 100 个字符。输出描述由若干行组成,前几行由空......
  • 字符串回文
    \(Manacher\)(马拉车)作用:可以在线性复杂度下求出每个点的最长回文半径算法流程:step1.\(manacher\)只能解决有对称中心的回文串,因此需要将所有回文串转化为有对称中心的,具体操作就是在每两个字符之间插入一个无关字符,并在首尾都插入无关字符step2.从左到右依次处理,记......
  • Java开发手册中-要求日志输出时字符串变量之间的拼接使用占位符与使用字符串拼接性能
    场景Java中使用JMH(JavaMicrobenchmarkHarness微基准测试框架)进行性能测试和优化:https://blog.csdn.net/BADAO_LIUMANG_QIZHI/article/details/131723751参考以上性能测试工具的使用。Java开发手册中有这样一条:【强制】在日志输出时,字符串变量之间的拼接使用占位符的方式......
  • Leetcoede编程基础0到1——1768. 交替合并字符串& 389. 找不同
    1768.交替合并字符串题目描述:给你两个字符串 word1 和 word2 。请你从 word1 开始,通过交替添加字母来合并字符串。如果一个字符串比另一个字符串长,就将多出来的字母追加到合并后字符串的末尾。返回 合并后的字符串 。输入输出实例:  示例1:输入:word1="ab......
  • Excel系列---【如何给一列字符串,在首尾快速加上双引号】
    你可以按照以下步骤将这个公式从A1应用到A164,并将结果生成到C1到C164:例如A1的内容为hello,在C1单元格中输入以下公式:=""""&A1&""","按下回车键后,C1单元格会显示A1单元格内容的修改结果,结果为"hello",。选中C1单元格,然后将鼠标放在单元格右下角的小黑点上,当鼠标变成十字形时,按......
  • C++:哈希表特性及开散列哈希表的模拟实现
    目录一、unordered_map1.1特性1.2接口1.21构造函数1.22 iteratorfind(constK& key)1.23 insert1.24 operator[]1.25 erase1.26find1.3哈希概念1.31闭散列哈希表1.32开散列哈希表二、部分功能模拟实现hashtable.hunordered_map.hunordered_set.h......