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

最长对称子串 --哈希算法求 详细注释

程序员文章站 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;
}