Finding Palindromes(POJ-3376)

题面

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.

输入

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.

输出

Print out only one integer, the number of palindromes.

样例输入

13
21 a
32 ab
42 ba

样例输出

15

提示

The 5 palindromes are: aa aba aba abba baab

思路

把所有正串都加进一棵Trie，然后用每个串的逆串去跑Trie，此时会出现以下情况：

  1. 匹配完成，那么就说明存在一个正串的前缀是这个逆串。如果剩余的逆串回文，那么能形成回文。
  2. 匹配失败，Trie未结束，说明不能构成回文。
  3. Trie已经跑到叶子节点，匹配未结束，那么如果正串剩余部分回文，那么能形成回文。

用扩展KMP处理出一个串的每个后缀是不是回文串，方法是用该串和其逆串仅用扩展KMP匹配，如果ex[i]=（从i到末尾的长度），那么说明从i到末尾的后缀是回文的。

代码

 1char s[mxn], t[mxn], rev[mxn];
 2int nxt[mxn], extend[mxn];
 3int tree[mxn][26], exist[mxn], cnt = 0;
 4int len[mxn], val[mxn];
 5LL ans = 0;
 6
 7void getnxt(char* t, int m)
 8{
 9    int a, p; nxt[0] = m;
10    for (int i=1, j=-1; i<m; i++, j--)
11    {
12        if (j<0 || i+nxt[i-a] >= p)
13        {
14            if (j<0) p = i, j = 0;
15            while (p<m && t[p]==t[j]) p++, j++;
16            nxt[i] = j, a = i;
17        } else
18            nxt[i] = nxt[i-a];
19    }
20}
21
22void exKMP(char* s, char* t, int n, int m)
23{
24    int a, p;
25    for (int i=0, j=-1; i<n; i++, j--)  //j即等于p与i的距离，其作用是判断i是否大于p（如果j<0，则i大于p）
26    {
27        if (j<0 || i+nxt[i-a] >= p)
28        {
29            if (j<0) p = i, j = 0;      //如果i大于p
30            while (p<n && j<m && s[p]==t[j]) p++, j++;
31            extend[i] = j, a = i;
32        } else
33            extend[i] = nxt[i-a];
34    }
35}
36
37void insert(char *s, int n)
38{
39    int p = 0;
40    for (int i=0; i<n; i++)
41    {
42        int c = s[i] - 'a';
43        if (!tree[p][c]) tree[p][c] = ++cnt;
44        p = tree[p][c];
45        val[p] += (i+1<n && extend[i+1]==n-i-1) ? 1 : 0;
46    }
47    exist[p]++;
48}
49
50int search(char *s, int n)
51{
52    int p = 0;
53    for (int i=0; i<n; i++)
54    {
55        int c = s[i] - 'a';
56        if (!tree[p][c]) return 0;
57        p = tree[p][c];
58        ans += (exist[p] && (i+1>=n || extend[i+1]==n-i-1)) ? exist[p] : 0;
59    }
60    ans += val[p];
61    return exist[p];
62}
63
64int main()
65{
66    int n; scanf("%d", &n);
67    int st = 0;
68    for(int i=0; i<n; i++){
69        scanf("%d %s", &len[i], s+st);
70        for(int j=0; j<len[i]; j++)
71            rev[j] = s[st+len[i]-j-1];
72        getnxt(rev, len[i]);
73        exKMP(s+st, rev, len[i], len[i]);
74        insert(s+st, len[i]);
75        st += len[i];
76    }
77    ans = st = 0;
78    for(int i=0; i<n; i++){
79        for(int j=0; j<len[i]; j++)
80            rev[j] = s[st+len[i]-j-1];
81        getnxt(s+st, len[i]);
82        exKMP(rev, s+st, len[i], len[i]);
83        search(rev, len[i]);
84        st += len[i];
85    }
86    printf("%lld\n", ans);
87    return 0;
88}