Time Limit: 10000MS | Memory Limit: 262144K | |
Total Submissions:4710 | Accepted: 879 | |
Case Time Limit: 2000MS |
Description
A word is called a palindrome if we read from right to left is as same as we read from left to right. For example, "dad", "eye" and "racecar" are all palindromes, but "odd", "see" and "orange" are not palindromes.
Given n strings, you can generate n × n pairs of them and concatenate the pairs into single words. The task is to count how many of the so generated words are palindromes.
Input
The first line of input file contains the number of strings n. The following n lines describe each string:
The i+1-th line contains the length of the i-th string li, then a single space and a string of li small letters of English alphabet.
You can assume that the total length of all strings will not exceed 2,000,000. Two strings in different line may be the same.
Output
Print out only one integer, the number of palindromes.
Sample Input
3
1 a
2 ab
2 ba
Sample Output
5
Hint
aa aba aba abba baab
Source
#include<iostream>
//#include<bits/stdc++.h>
#include<cstdio>
#include<cmath>
//#include<cstdlib>
#include<cstring>
#include<algorithm>
//#include<queue>
#include<vector>
//#include<set>
//#include<climits>
//#include<map>
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
#define N 100010
#define pi 3.1415926535
#define inf 0x3f3f3f3f const int maxn = 2e6 + ;
int n, sum_len;
char s[maxn], s_rev[maxn];
int st[maxn], ed[maxn]; int nxt[maxn], ex[maxn];
bool flag[][maxn];
void GETNEXT(char *str, int l, int r)
{
int i=l,j,po;
nxt[i]=r - l + ;//初始化next[0]
while(str[i]==str[i+]&&i<=r)//计算next[1]
i++;
nxt[l + ]=i - l;
po= + l;//初始化po的位置
for(i=+l;i<=r;i++)
{
if(nxt[i-po + l]+i - l<nxt[po]+po - l)//第一种情况,可以直接得到next[i]的值
nxt[i]=nxt[i-po + l];
else//第二种情况,要继续匹配才能得到next[i]的值
{
j=nxt[po]+po-i;
if(j<)j=;//如果i>po+next[po],则要从头开始匹配
while(i+j<=r&&str[l+j]==str[j+i])//计算next[i]
j++;
nxt[i]=j;
po=i;//更新po的位置
}
}
}
//计算extend数组
void EXKMP(char *s1,char *s2, int l, int r, int sign)
{
int i=l,j,po;
GETNEXT(s2, l, r);//计算子串的next数组
//for(j = l; j <= r; j++)cout<<nxt[j]<<endl;
while(s1[i]==s2[i]&&i<=r)//计算ex[0]
i++;
ex[l]=i - l;
po=l;//初始化po的位置
for(i=l + ;i<=r;i++)
{
if(nxt[i-po + l]+i - l<ex[po]+po -l)//第一种情况,直接可以得到ex[i]的值
ex[i]=nxt[i-po+l];
else//第二种情况,要继续匹配才能得到ex[i]的值
{
j=ex[po]+po-i;
if(j<)j=;//如果i>ex[po]+po则要从头开始匹配
while(i+j<=r&&s1[j+i]==s2[l+j])//计算ex[i]
j++;
ex[i]=j;
po=i;//更新po的位置
}
}
for(int i = l; i <= r; i++){
//cout<<ex[i]<<endl;
if(ex[i] == r - i + ){
flag[sign][i] = true;
}
}
} struct Trie{
int trie[maxn][];
int cnt[maxn];
int val[maxn];
int tot;
}tr; void init()
{
memset(flag, , sizeof(flag));
memset(nxt, , sizeof(nxt));
memset(ex, , sizeof(ex));
for(int i = ; i <= tr.tot; i++){
memset(tr.trie[i], , sizeof(tr.trie[i]));
tr.cnt[i] = ;
tr.val[i] = ;
}
tr.tot = ;
} void insertt(char *str, int l, int r)
{
int p = ;
for(int k = l; k <= r; k++){
int ch = str[k] - 'a';
tr.val[p] += flag[][k];
if(tr.trie[p][ch] == ){
tr.trie[p][ch] = ++tr.tot;
}
p = tr.trie[p][ch]; }
tr.cnt[p]++;
} LL searchh(char *str, int l, int r)
{
LL ans = ;
int p = ;
for(int k = l; k <= r; k++){
//cout<<flag[k]<<endl;
int ch = str[k] - 'a';
p = tr.trie[p][ch];
if(p == )break;
if(k < r && flag[][k + ] || k == r)ans += tr.cnt[p];
}
if(p)ans += tr.val[p];
//ans += tr.cnt[p];
return ans;
} int main()
{
while(scanf("%d", &n) != EOF){
sum_len = ;
init();
for(int i = ; i < n; i++){
int l;
scanf("%d %s", &l, s + sum_len);
for(int j = ; j < l; j++){
s_rev[sum_len + j] = s[sum_len + l - - j];
}
st[i] = sum_len;
sum_len += l;
ed[i] = sum_len - ; EXKMP(s, s_rev, st[i], ed[i], );
EXKMP(s_rev, s, st[i], ed[i], );
insertt(s, st[i], ed[i]);
} LL ans = ;
/*for(int i = 0; i < sum_len; i++){
cout<<s[i]<<" "<<flag[0][i]<<" "<<flag[1][i]<<endl;
}*/
//cout<<s<<endl;
for(int i = ; i < n; i++){
ans += searchh(s_rev, st[i], ed[i]);
}
printf("%lld\n", ans);
}
return ;
}