POJ3376 Finding Palindromes —— 扩展KMP + Trie树

题目链接：https://vjudge.net/problem/POJ-3376

Finding Palindromes

Time Limit: 10000MS		Memory Limit: 262144K
Total Submissions: 4244		Accepted: 796
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 l_i, then a single space and a string of l_i 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

Hint

The 5 palindromes are:
aa aba aba abba baab

Source

POJ Monthly--2007.09.09, Zhou Gelin, modified from POI06

题解：

可知：如果两字符串拼接起来能够形成回文串，那么短串的逆串是长串的前缀。

根据上述结论，我们可以：

1.利用扩展KMP算法求出每个字符串的后缀是否为回文串，以及每个字符串的逆串的后缀是否为回文串。

2.将每个字符串插入到Trie树中，并且Trie树的结点需要维护两个信息：当前结点的字符串数，以及往下有多少个回文串后缀。

3.用每个字符串的逆串去Trie树中查找。有两种情况：当前串作为长串，以及当前串作为短串。详情请看代码。

代码如下：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cstdlib>
  5 #include <string>
  6 #include <vector>
  7 #include <map>
  8 #include <set>
  9 #include <queue>
 10 #include <sstream>
 11 #include <algorithm>
 12 using namespace std;
 13 typedef long long LL;
 14 const double eps = 1e-6;
 15 const int INF = 2e9;
 16 const LL LNF = 9e18;
 17 const int MAXN = 2e6+10;
 18 
 19 char str[MAXN], res[MAXN];
 20 int beg[MAXN], len[MAXN], ispal[2][MAXN];
 21 int Next[MAXN], exd[MAXN];
 22 
 23 struct Node
 24 {
 25     int strnum;
 26     int palnum;
 27     int nxt[26];
 28 };
 29 Node node[MAXN];
 30 int tot, root;
 31 
 32 int newnode()
 33 {
 34     node[tot].strnum = 0;
 35     node[tot].palnum = 0;
 36     memset(node[tot].nxt, -1, sizeof(node[tot].nxt));
 37     tot++;
 38     return tot-1;
 39 }
 40 
 41 void pre_EXKMP(char x[], int m)
 42 {
 43     Next[0] = m;
 44     int j = 0;
 45     while(1+j<m && x[0+j]==x[1+j]) j++;
 46     Next[1] = j;
 47     int k = 1;
 48     for(int i = 2; i<m; i++)
 49     {
 50         int p = Next[k]+k-1;
 51         int L = Next[i-k];
 52         if(i+L<=p) Next[i] = L;
 53         else
 54         {
 55             j = max(0, p-i+1);
 56             while(i+j<m && x[i+j]==x[0+j]) j++;
 57             Next[i] = j;
 58             k = i;
 59         }
 60     }
 61 }
 62 
 63 void EXKMP(char x[], int m, char y[], int n, int _L, int type)
 64 {
 65     pre_EXKMP(x, m);
 66     int j = 0;
 67     while(j<n && j<m && x[j]==y[j]) j++;
 68     exd[0] = j;
 69     int k = 0;
 70     for(int i = 1; i<n; i++)
 71     {
 72         int p = exd[k]+k-1;
 73         int L = Next[i-k];
 74         if(i+L<=p) exd[i] = L;
 75         else
 76         {
 77             j = max(0,p-i+1);
 78             while(i+j<n && j<m && y[i+j]==x[0+j]) j++;
 79             exd[i] = j;
 80             k = i;
 81         }
 82     }
 83 
 84     //当type为0时，求的是字符串的后缀是否为回文串
 85     //当type为1时，求的是字符串的逆串是否为回文串。实际就是求字符串的前缀是否为回文串。
 86     for(int i = 0; i<n; i++)    //判断后缀是否为回文串
 87         ispal[type][_L+i] = (i+exd[i]==n);
 88 }
 89 
 90 void insert(char x[], int n, int L)
 91 {
 92     int tmp = root;
 93     for(int i = 0; i<n; i++)
 94     {
 95         int ch = x[i]-'a';
 96         node[tmp].palnum += ispal[0][L+i];  //如果后缀是回文串，就把统计数放在父节点。
 97         if(node[tmp].nxt[ch]==-1) node[tmp].nxt[ch] = newnode();
 98         tmp = node[tmp].nxt[ch];
 99     }
100     node[tmp].strnum++; //字符串数+1
101 }
102 
103 int search(char x[], int n, int L)
104 {
105     int ret = 0;
106     int tmp = root;
107     for(int i = 0; i<n; i++)
108     {
109         int ch = x[i]-'a';
110         tmp = node[tmp].nxt[ch];
111         if(tmp==-1) break;
112         if((i<n-1&&ispal[1][L+i+1]) || i==n-1)  //x作为长串，如果剩下的部分（后缀）是回文串
113             ret += node[tmp].strnum;
114     }
115     if(tmp!=-1)  ret += node[tmp].palnum;   //x作为短串，加上后缀是回文串的长串
116     return ret;
117 }
118 
119 int main()
120 {
121     int n;
122     while(scanf("%d", &n)!=EOF)
123     {
124         tot = 0;
125         root = newnode();
126 
127         int L = 0;
128         memset(ispal, 0, sizeof(ispal));
129         for(int i = 0; i<n; i++)
130         {
131             //因为不确定每个字符串的最长长度，所以只好用地址的形式存储字符串
132             //用string的话，速度会变慢
133             scanf("%d%s", &len[i], str+L);
134             beg[i] = L;
135             L += len[i];
136             memcpy(res+beg[i], str+beg[i], len[i]);
137             reverse(res+beg[i], res+beg[i]+len[i]);
138 
139             EXKMP(res+beg[i], len[i], str+beg[i], len[i], beg[i], 0);   //求字符串后缀是否为回文串
140             EXKMP(str+beg[i], len[i], res+beg[i], len[i], beg[i], 1);   //求字符串的逆串的后缀（即字符串的前缀）是否为回文串。
141             insert(str+beg[i], len[i], beg[i]);     //插入Trie树中
142         }
143 
144         LL ans = 0;
145         for(int i = 0; i<n; i++)
146             ans += search(res+beg[i], len[i], beg[i]);  //用字符串的逆串去查找
147 
148         printf("%lld
", ans);
149     }
150 }

View Code