[POI 2010] ANT-Antisymmetry

链接

好像回文串的子串问题,似乎可以用马拉车算法(manacher)来写

这道题本质上就是看左右对称的两点处的值和是否为1(对应回文串的相等)

但是,与回文串不同的是,奇数的串显然不符合题意,因此我们只需要考虑偶数串即可

我们得到以每个点为中心的最长符合题意的字符串之后

我们发现,只要是以该处为中心,任意长度小于最长半径的字符串都符合题意

比如111000,中心是0(由于偶数的中心很尴尬,我们取右边一个)

那么,1100,10都符合题意

因此我们只需要将得到的半径相加即可

代码如下:

#include<iostream>
#include<vector>
using namespace std;

long long manacher(string& s) {
	int n = s.size();
	vector<int>a(n);
	int l = 0, r = -1;
	for (int i = 0;i < n;i++) {
		int k = i > r ? 0 : min(a[r + l - i + 1], r - i + 1);
		while (i - k - 1 >= 0 && i + k < n && s[i - k - 1] + s[i + k] == '0' + '1') k++;
		a[i] = k;
		if (i + k - 1 > r) {
			l = i - k;
			r = i + k - 1;
		}
	}
	long long res = 0;
	for (int i = 0;i < n;i++) {
		res += a[i];
	}
	return res;
}

int main() {
	int n;
	cin >> n;
	string str;
	cin >> str;
	cout << manacher(str);
}

时间复杂度:O(n)

空间复杂度:O(n)

当然,这题还能用哈希写(本来就是我用来练哈希的)

我们设置两个哈希h和rh

h记录的是原字符串的某个进制

rh记录的是原字符串变换(1变成0,0变成1)后再反转的某个进制

接着用二分法求出最大半径(怎么求?我比对二者的哈希值是否相等就行了,不过要注意,rh和h是对称的)

代码如下:

#include<vector>
using namespace std;
#define ull unsigned long long
const int base = 233;
vector<ull>h, rh, b;


ull f(string& s, string& rs) {
	int n = s.size();
	ull res = 0;
	for (int i = 1;i <= n;i++) {
		int l = 0, r = min(i - 1, n - i + 1);
		int ans = 0;
		while (r >= l) {
			int mid = (l + r) / 2;
			int right = i + mid - 1, left = i - mid;
			ull h1, h2;
			h1 = h[right] - h[left - 1] * b[right - left + 1];
			h2 = rh[n - left + 1] - rh[n - right] * b[right - left + 1];
			if (h1 != h2) {
				r = mid - 1;
			}
			else {
				l = mid + 1;
				ans = mid;
			}
		}
		res += ans;
	}
	return res;
}


int main() {
	int n;
	string str;
	cin >> n >> str;
	h.assign(n + 1, 1);
	rh.assign(n + 1, 1);
	b.assign(n + 1, 1);
	string rs;
	for (int i = n - 1;i >= 0;i--) {
		rs += str[i] == '1' ? '0' : '1';
	}
	for (int i = 1;i <= n;i++) {
		b[i] = b[i - 1] * base;
		h[i] = h[i - 1] * base + str[i - 1] - 'a';
		rh[i] = rh[i - 1] * base + rs[i - 1] - 'a';
	}
	cout << f(str, rs);
}

时间复杂度:O(n log n)

空间复杂度:O(n)