Queries for Number of Palindromes

wjh15101051's space

卧薪尝胆，厚积薄发。

Date: Wed Jan 16 08:15:49 CST 2019

In Category: NoCategory

Description：

一个字符串 $s$ ，有 $q$ 组询问，每次询问在字符串区间 $l$ 到 $r$ 的字串中，包含多少回文串。

$1\leqslant n\leqslant 5000,1\leqslant q\leqslant 10^6$

Solution：

考虑预处理所有答案，枚举左端点，依次扩展右端点，并同时维护回文树，那么新的右端点的贡献就是 $cnt[last]$ ，其中 $cnt[i]=cnt[s[i].fail]+1$ 。

Code：


#include<bits/stdc++.h>

using namespace std;

int n;

#define MAXN 5010

char c[MAXN];

int ans[MAXN][MAXN];

struct node

{

	int tr[26];

	int len,fail;

}s[MAXN];

int ptr,last;

int newnode(int l){s[ptr].len = l;return ptr++;}

int cnt[MAXN];

void init()

{

	ptr = last = 0;

	memset(s,0,sizeof(s));

	memset(cnt,0,sizeof(cnt));

	newnode(0);newnode(-1);

	s[0].fail = 1;

	return;

}

int getfail(int i,int p)

{

	while(c[i - s[p].len - 1] != c[i])p = s[p].fail;

	return p;

}

int res = 0;

void extend(int i,int k)

{

	int p = getfail(i,last);

	if(s[p].tr[k] == 0)

	{

		int np = newnode(s[p].len + 2);

		s[np].fail = s[getfail(i,s[p].fail)].tr[k];

		s[p].tr[k] = np;

		cnt[np] = cnt[s[np].fail] + 1;

	}

	last = s[p].tr[k];

	res += cnt[last];

	return;

}

int main()

{

	scanf("%s",c + 1);

	n = strlen(c + 1);

	for(int l = 1;l <= n;++l)

	{

		init();

		res = 0;

		for(int r = l;r <= n;++r)

		{

			extend(r,c[r]);

			ans[l][r] = res;

		}

		c[l] = -1;

	}

	scanf("%d",&n);

	int l,r;

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

	{

		scanf("%d%d",&l,&r);

		printf("%d\n",ans[l][r]);

	}

	return 0;

}

In tag: 字符串-回文自动机

wjh15101051