【BZOJ】1524: [POI2006]Pal

题意

给出\(n\)个回文串\(s_i(\sum_{i=1}^{n} |s_i| \le 2000000)\)求如下二元组\((i, j)\)的个数\(s_i + s_j\)仍然是回文串。

分析

这道题其实是一道傻逼hash题，可是为了学习拓展kmp我就写了拓展kmp。

其实我们考虑\(a+b\)如果是回文串，那么\(a\)的前缀肯定和倒过来的\(b\)的后缀相等，然后剩下的肯定也是一个回文串。那么这题就解决了。

题解

将每一个串倒序插入到trie中。然后正序遍历每一个串，然后判断剩下的是否是回文串即可，剩下的是否是回文串可以用拓展kmp，也可以用hash。不过如果用hash的话还有一个更快的方法，就是枚举回文中心，然后统计左边和右边相等的个数，请自己yy把。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=2000005;

char s[N+N], rs[N+N], Buf[N+N], *buf=Buf;

int A[N+N], *a=A, c[N][26], tot, sum[N], w[N], nn[N+N];

void getp(char *a, char *b, int na, int nb, int *p, int *q, int flag) {

	int add=flag==2;

	q[1]=add?na:0;

	q[flag]=0;

	for(int i=1, g=min(na, nb)-add, &now=q[flag]; i<=g && a[i]==b[i+add]; ++i, ++now);

	for(int i=1+flag, x=flag, y=flag+q[flag]-1; i<=na; ++i) {

		int L=p[i-x+1], &now=q[i];

		if(i+L<=y) {

			now=L;

		}

		else {

			y=max(y, i-1);

			x=i;

			now=y-i+1;

			for(; y<na && now<nb && b[now+1]==a[y+1]; ++now, ++y);

		}

	}

}

void getq(char *a, char *b, int na, int nb, int *q) {

	static int p[N];

	getp(b, b, nb, nb, p, p, 2);

	getp(a, b, na, nb, p, q, 1);

}

inline int getint() {

	int x=0;

	char ch=*buf++;

	for(; ch<'0'||ch>'9'; ch=*buf++);

	for(; ch>='0'&&ch<='9'; x=x*10+ch-'0', ch=*buf++);

	return x;

}

int main() {

	fread(Buf, 1, sizeof Buf, stdin);

	int T=getint();

	char *ts=s;

	for(int t=0; t<T; ++t) {

		int n=getint(), x=0;

		char *ns=ts++, ch=*buf++;

		for(; ch<'a'||ch>'z'; ch=*buf++);

		for(; ch>='a'&&ch<='z'; *ts++=ch, ch=*buf++);

		for(int i=1; i<=n; rs[i]=ns[n-i+1], ++i);

		rs[n+1]=0;

		getq(rs, ns, n, n, a);

		a[n+1]=-1;

		for(int i=1; i<=n; ++i) {

			int y=rs[i]-'a';

			if(!c[x][y]) {

				c[x][y]=++tot;

			}

			sum[x=c[x][y]]+=a[i+1]==n-i;

		}

		getq(ns, rs, n, n, a);

		a[n+1]=0;

		++w[x];

		a+=n+1;

		nn[t]=n;

	}

	ll ans=0;

	ts=s;

	a=A;

	for(int t=0, x=0, n, i; t<T; ++t) {

		char *ns=ts++;

		n=nn[t];

		for(i=1, x=0; *ts && (x=c[x][*ts-'a']); ++ts, ++i) {

			ans+=w[x]*(a[i+1]==n-i);

		}

		if(x) {

			ans+=sum[x];

		}

		ts=ns+n+1;

		a+=n+1;

	}

	printf("%lld\n", ans);

	return 0;

}

巴特西

【BZOJ】1524: [POI2006]Pal

题意

分析

题解

最新文章

热门文章