题目大意:
就是现在给出一个字符串s, 长度不超过 10^5, 然后求出其中不相交的回文字串的对数
大致思路:
其实一眼看去就知道可以用Manacher处理出回文半径之后用前缀和解决 不过有想了一下Palindromic Tree的做法, 算是练习一下Palindromic Tree了
解法一:
Manacher处理出所有位置的回文半径然后计算以i位置结尾的回文串数量和以i位置开始的回文串数量, 然后其中一组乘上另外一组的前缀和加起来就是答案了
代码如下:
Result : Accepted Memory : 6016 KB Time : 109 ms
/*
* Author: Gatevin
* Created Time: 2015/3/31 10:03:33
* File Name: Rin_Tohsaka.cpp
*/
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#include<iomanip>
using namespace std;
const double eps(1e-8);
typedef long long lint;
#define maxn 100010
char in[maxn];
char s[maxn << 1];
int R[maxn << 1];
lint dp1[maxn], dp2[maxn], s1[maxn], s2[maxn];
void Manacher(char *s, int *R, int n)
{
int mx = 0, p = 0;
R[0] = 1;
for(int i = 1; i <= n; i++)
{
if(mx > i) R[i] = min(R[2*p - i], mx - i);
else R[i] = 1;
while(s[i - R[i]] == s[i + R[i]])
R[i]++;
if(i + R[i] > mx)
mx = i + R[i], p = i;
}
return;
}
int main()
{
while(scanf("%s", in) != EOF)
{
s[0] = '@';
int n = strlen(in);
for(int i = 0; i < n; i++)
s[2*i + 1] = in[i], s[2*i + 2] = '#';
s[2*n] = '$';
Manacher(s, R, 2*n);
memset(dp1, 0, sizeof(dp1));
memset(dp2, 0, sizeof(dp2));
for(int i = 1; i < 2*n; i++)
{
int l = i - R[i] + 1, r = i;
l >>= 1;
r = (r & 1) ? r >> 1 : (r >> 1) - 1;
if(l <= r)
dp1[l]++, dp1[r + 1]--;
l = i;
r = i + R[i] - 1;
l >>= 1;
r = (r & 1) ? r >> 1 : (r >> 1) - 1;
if(l <= r)
dp2[l]++, dp2[r + 1]--;
}
//用s1[i]表示以第i个字符开头的回文串数量
//用s2[i]表示以第i个字符结尾的回文串数量
s1[0] = dp1[0], s2[0] = dp2[0];
for(int i = 1; i < n; i++)
s1[i] = s1[i - 1] + dp1[i], s2[i] = s2[i - 1] + dp2[i];
//滚动数组用dp1表示s1的后缀和
dp1[n - 1] = s1[n - 1];
for(int i = n - 2; i >= 0; i--)
dp1[i] = dp1[i + 1] + s1[i];
lint ans = 0;
for(int i = 0; i < n - 1; i++)
ans += s2[i]*dp1[i + 1];
printf("%I64d\n", ans);
}
return 0;
}
解法二:
用Palindromic Tree 来计算上面那种方法中的s1, s2 (就是把串s插入树中两次, 一次正序一次倒序就行了, 计数思想一样), 只是得到s1, s2的手段不同罢了
代码如下:
Result : Accepted Memory : 14048 KB Time : 109 ms
/*
* Author: Gatevin
* Created Time: 2015/3/31 10:34:41
* File Name: Rin_Tohsaka.cpp
*/
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#include<iomanip>
using namespace std;
const double eps(1e-8);
typedef long long lint;
#define maxn 100010
char s[maxn];
lint dp[maxn];
struct Palindromic_Tree
{
struct node
{
int next[26];
int len;
int sufflink;
int cnt;
};
node tree[maxn];
int L, len, suff;
void newnode()
{
L++;
for(int i = 0; i < 26; i++)
tree[L].next[i] = -1;
tree[L].len = tree[L].sufflink = tree[L].cnt = 0;
return;
}
void init()
{
L = 0, suff = 2;
newnode(), newnode();
tree[1].len = -1; tree[1].sufflink = 1;
tree[2].len = 0; tree[2].sufflink = 1;
return;
}
bool addLetter(int pos)
{
int cur = suff, curlen = 0;
int alp = s[pos] - 'a';
while(1)
{
curlen = tree[cur].len;
if(pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos])
break;
cur = tree[cur].sufflink;
}
if(tree[cur].next[alp] != -1)
{
suff = tree[cur].next[alp];
return false;
}
newnode();
suff = L;
tree[L].len = tree[cur].len + 2;
tree[cur].next[alp] = L;
if(tree[L].len == 1)
{
tree[L].sufflink = 2;
tree[L].cnt = 1;
return true;
}
while(1)
{
cur = tree[cur].sufflink;
curlen = tree[cur].len;
if(pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos])
{
tree[L].sufflink = tree[cur].next[alp];
break;
}
}
tree[L].cnt = 1 + tree[tree[L].sufflink].cnt;
return true;
}
};
Palindromic_Tree pal;
int main()
{
while(scanf("%s", s) != EOF)
{
pal.init();
int n = strlen(s);
for(int i = 0; i < n; i++)
{
pal.addLetter(i);
dp[i] = pal.tree[pal.suff].cnt;//dp[i]表示以i位置结尾的回文串的数量
}
for(int i = 1; i < n; i++)
dp[i] += dp[i - 1];//现在dp[i]表示在i位置或之前结尾的回文串数量
reverse(s, s + n);
pal.init();
lint ans = 0;
for(int i = 0; i < n; i++)
{
pal.addLetter(i);
ans += pal.tree[pal.suff].cnt*dp[n - 1 - i - 1];
}
printf("%I64d\n", ans);
}
return 0;
}