最长对称子串 --哈希算法求 详细注释
程序员文章站
2022-07-13 21:53:56
...
题解
常规做法和哈希做法在时间复杂度上有很大的差距
哈希做法会快很多很多
1.正向 反向 都求其映射值
2.枚举中心点
3.二分法求半径 看两边的映射值
哈希算法很常用 最后要知道 可以先去搜一下哈希的作用
正常做法
哈希
时间差的还是蛮多的
注释很详细
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
using ULL = unsigned long long;
ULL h1[2005], h2[2005], base = 13331, p[2000];
bool check(int a, int b, int c, int d)
{
//求哈希值
//——————b是高位 a是低位 先左移 然后乘他们的之间相差的权值
int x = h1[b] - h1[a - 1] * p[b - a + 1];
//——————c其实是高位 因为存的时候反着存的 d右移
int y = h2[c] - h2[d + 1] * p[d - c + 1];
return x == y;
}
int main()
{
string str, s;
getline(cin, str);
s = "`";
for (auto c : str)
{
s.push_back(c);
s.push_back('`');
}
p[0] = 1;
//开头和结尾的 ` 去掉
int n = s.size() - 2;
// cout << n << ' ' << s<<' '<<str.size();
for (int i = 1, j = n; i <= n; ++i, --j)
{
//正序哈希值
h1[i] = h1[i - 1] * base + s[i];
//逆序哈希值
h2[j] = h2[j + 1] * base + s[j];
//权值
p[i] = p[i - 1] * base;
}
int ans = -1;
//尝试半径
for (int i = 1; i <= n; ++i)
{
//———————————R是最大半径的长度 在左半边的时候 和 在右半边的时候
int L = 0, R = min(i - 1, n - i);
while (L < R)
{
int mid = (L + R + 1) / 2;
//这个半径可以
//左半径 i-mid -> i 右半径 i -> i+mid
if (check(i - mid, i, i, i + mid))
L = mid;
else
//这个不可以 尝试半径更小的
R = mid - 1;
}
//看边上的字符是不是特殊字符
if (s[i - L] != '`')
++L;
// L明明是半径为什么还直接当直径来比较呢???
//其实啊 前面加入了特殊字符 所以呢...嗯
//总长度是 2L+1 [(2L+1)/2] 上取整 就是L+1了
//然后上面的code 也判断了边上的一个字符是不是
ans = max(ans, L);
}
cout << ans << endl;
return 0;
}
上一篇: PTA 最长对称子串
下一篇: 字符串排序问题