ybtoj·回文子串【Hash】

回文子串

• • Description--
  • 解題思路--
  • 代碼--

Description–

高效進階「字元串算法」第2章 Hash 和 Hash 表課堂過關 例題2

解題思路–

用字首和的方式正反記錄字元串，即可實作快速查詢一個串的哈希值

枚舉每一個中心點i，則有兩種情況：

• 以i點為中心，回文串的長度是奇數
• 以i點和i+1點中間的軸為中心，回文串的長度是偶數

然後二分求延伸的長度

代碼–

#include <iostream>
#include <cstring> 
#include <cstdio>
#define ull unsigned long long

using namespace std;

const int M = 1100000;

string c;
int n, g, ans;
ull ha[M], ha1[M], ha2[M];

void work(int lev)
{
	ans = 0;
	ha1[0] = c[0] - 'a' + 1;
	for (int i = 1; i < n; ++i)
	  ha1[i] = ha1[i - 1] * 131 + (c[i] - 'a' + 1);
	ha2[n - 1] = c[n - 1] - 'a' + 1;
	for (int i = n - 2; i >= 0; --i)
	  ha2[i] = ha2[i + 1] * 131 + (c[i] - 'a' + 1);
	for (int i = 0; i < n; ++i)
	{
		int l = 0, r = n - 1;
		while (l <= r)
		{
			int mid = (l + r) >> 1;
			if (i - mid < 0 || i + mid > n - 1)
			  r = mid - 1;
			else if (ha1[i - 1] - ha1[i - 1 - mid] * ha[mid] == ha2[i + 1] - ha2[i + 1 + mid] * ha[mid])
			{
				ans = max(ans, mid * 2 + 1);
				l = mid + 1;
			}
			else r = mid - 1;
		}
		l = 0, r = n - 1;
		while (l <= r)
		{
			int mid = (l + r) >> 1;
			if (i - mid  + 1 < 0 || i + mid > n - 1)
			  r = mid - 1;
			else if (ha1[i] - ha1[i - mid] * ha[mid] == ha2[i + 1] - ha2[i + 1 + mid] * ha[mid])
			{
				ans = max(ans, mid * 2);
				l = mid + 1;
			}
			else r = mid - 1;
		}
	}
	printf("Case %d: %d\n", lev, ans);
}

int main()
{
	cin >> c;
	ha[0] = 1;
	for (int i = 1; i <= 1000000; ++i)
	  ha[i] = ha[i - 1] * 131;
	while (c != "END")
	{
		g++, n = (int)c.size();
		memset(ha1, 0, sizeof(ha1));
		memset(ha2, 0, sizeof(ha2));
		work(g);
		cin >> c;
	}
	
	return 0;
}