【C++】字符串|比较类问题模板
这一篇文章主要涉及到字符串间进行比较、判断相等等问题的算法。
字符串哈希
哈希hash：哈希函数又叫散列函数，简单说就是把一段任意字符映射为一个与之对应的整数。要求字符串与数字一一对应。密码学和项目中常见的md5，sha1，sha256都是现代常用的哈希算法（均不可逆，均用16进制数表示）
竞赛中使用的是最基本的，基于质数映射的哈希函数。
题目：P3370 【模板】字符串哈希（https://www.luogu.com.cn/problem/P3370）
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
using ull = unsigned long long;
// A naive prime
constexpr int prime = 19260817;
ull gethash(string& s)
{
ull cur = 0;
for (auto& i : s)
{
cur *= prime;
cur += i;
}
return cur;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n;
string tmp;
cin >> n;
vector<ull> sts;
int res = n;
while (n--)
{
cin >> tmp;
sts.emplace_back(gethash(tmp));
}
sort(sts.begin(), sts.end());
for (int i = 1; i < sts.size(); i++)
{
if (sts[i] == sts[i - 1]) res--;
}
cout << res << endl;
return 0;
}
哈希碰撞
上面提到了原字符串应与哈希结果一一对应（充要）。显然存在一些特殊的字符串，可以使得他们恰巧算出了同一个哈希值，这种现象就是哈希碰撞。
最小表示法
什么是最小表示法：一个字符串s经过轮换得到的字典序最小的串i，称i为s的最小表示。
例子：s="acacab", -> i="abacac";
很容易写出每种排列都试一下的暴力算法，但是显然这是O(n^2)的。
Booth 算法
存在一种O(n)的算法可以快速求出最小表示。主要思想与KMP类似，即利用已比较部分跳过无用部分。
题目：P13270 【模板】最小表示法（https://www.luogu.com.cn/problem/P13270）
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n;
string s;
cin >> n >> s;
int i = 1, j = 0, k = 0;
while (i < n && j < n)
{
for (k = 0; k < n; k++)
{
if (s[(i + k) % n] != s[(j + k) % n]) break;
}
if (s[(i + k) % n] > s[(j + k) % n]) i += k + 1;
else j += k + 1;
if (i == j) j++;
}
int res = min(i, j);
for (int x = res; x < res + n; x++)
{
cout << s[x % n];
}
cout << endl;
return 0;
}目前有关字符串的比较相关问题就这些内容。希望我以后遗忘可以慢一点。。。同时如果这也能帮到你，我很荣幸。真的。。
版权声明：
作者：Toms Project
链接：https://blog.projectoms.com/pages/1680.html
来源：Toms Project 官方博客
文章版权归作者所有，未经允许请勿转载。
共有 0 条评论