POJ 3376 Finding Palindromes EX-KMP+字典树

题意：

给你n个串串，每个串串可以选择和n个字符串拼接（可以自己和自己拼接），问有多少个拼接后的字符串是回文。

所有的串串长度不超过2e6；

题解：

这题由于是在POJ上，所以string也用不了，会tle。

 串串个数也比较多，开不下二维的char数组，卡内存。

所以数据的预处理需要处理成一个串串，把所有的串串放在一个串里面。

记录每一个串串的起始位置和长度。

数据预处理部分就解决了。

然后就是核心思想部分了。

首先你要知道如何用EX_KMP求串串前缀和后缀是否是回文。（其实也可以用马拉车）

其实这个就是t串等于s串的反串，然后做一个EX_KMP就可以了。

不会的可以做做这一题  Best Reward HDU - 3613

于是我们处理出了所有串串的前缀和后缀是否是一个回文。

下面看这个例子 dedabc 和 cba 这个显然就是可以拼接成回文的。

由此很容易想到用字典树写这一题。

然后有3种情况

1、s的长度 > t的长度，t的反串是s的前缀，s剩下的部分是回文串。

2、s的长度 < t的长度，s的反串是t的前缀，t剩下的部分是回文串。

3、s的长度 = t的长度，t的反串等于s。

然后就是具体做法，正串放入字典树内，如果某个位置的的下一个位置pos是一个回文（这个根据上面的EX_KMP处理出来）val[pos]++;

插入完后就在最后一个节点的位置pos，ed[pos]++；

最后一步计算答案；

字典树里面存的是正串，所以查询使用反串去进行匹配，

第1种情况，假设当前节点为u，对于当前节点i，当i<len-1且从第i+1个字母往后是一个回文串的时候，ans+=ed[u]。

第2种情况，如果我们顺利的查找到s反串的尾节点u，则ans+=val[u]。

第3种情况，假设当前节点为u，对于当前节点i，当i==len-1的时候，ans+=ed[u]。

 

最近正在学习串串，这是我遇到的第一道需要思考的题目，感觉还是可以的。

博客鸽了这么久，是时候开始写了。

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <queue>
  4 #include <cmath>
  5 #include <algorithm>
  6 #include <set>
  7 #include <iostream>
  8 #include <map>
  9 #include <stack>
 10 #include <string>
 11 #include <time.h>
 12 #include <vector>
 13 #define  pi acos(-1.0)
 14 #define  eps 1e-9
 15 #define  fi first
 16 #define  se second
 17 #define  rtl   rt<<1
 18 #define  rtr   rt<<1|1
 19 #define  bug         printf("******\n")
 20 #define  mem(a,b)    memset(a,b,sizeof(a))
 21 #define  name2str(x) #x
 22 #define  fuck(x)     cout<<#x" = "<<x<<endl
 23 #define  f(a)        a*a
 24 #define  sf(n)       scanf("%d", &n)
 25 #define  sff(a,b)    scanf("%d %d", &a, &b)
 26 #define  sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
 27 #define  sffff(a,b,c,d) scanf("%d %d %d %d", &a, &b, &c, &d)
 28 #define  pf          printf
 29 #define  FRE(i,a,b)  for(i = a; i <= b; i++)
 30 #define  FREE(i,a,b) for(i = a; i >= b; i--)
 31 #define  FRL(i,a,b)  for(i = a; i < b; i++)+
 32 #define  FRLL(i,a,b) for(i = a; i > b; i--)
 33 #define  FIN         freopen("data.txt","r",stdin)
 34 #define  gcd(a,b)    __gcd(a,b)
 35 #define  lowbit(x)   x&-x
 36 #define rep(i,a,b) for(int i=a;i<b;++i)
 37 #define per(i,a,b) for(int i=a-1;i>=b;--i)
 38 using namespace std;
 39 typedef long long  LL;
 40 typedef unsigned long long ULL;
 41 const int maxn = 2e6 + 7;
 42 const int maxm = 8e6 + 10;
 43 const int INF = 0x3f3f3f3f;
 44 const int mod = 10007;
 45 int nxt[maxn], extend[maxn], len[maxn], vis[2][maxn];
 46 char s[maxn], t[maxn];
 47 void pre_EKMP ( char x[], int m, int nxt[] ) {
 48     nxt[0] = m;
 49     int j = 0;
 50     while ( j + 1 < m && x[j] == x[j + 1] ) j++;
 51     nxt[1] = j;
 52     int k = 1;
 53     for ( int i = 2; i < m; i++ ) {
 54         int p = nxt[k] + k - 1;
 55         int L = nxt[i - k];
 56         if ( i + L < p + 1 ) nxt[i] = L;
 57         else {
 58             j = max ( 0, p - i + 1 );
 59             while ( i + j < m && x[i + j] == x[j] ) j++;
 60             nxt[i] = j;
 61             k = i;
 62         }
 63     }
 64 }
 65 void EKMP ( char x[], int m, char y[], int n, int nxt[], int extend[], int _L, int flag ) {
 66     pre_EKMP ( x, m, nxt );
 67     int j = 0;
 68     while ( j < n && j < m && x[j] == y[j] ) j++;
 69     extend[0] = j;
 70     int k = 0;
 71     for ( int i = 1; i < n; i++ ) {
 72         int p = extend[k] + k - 1;
 73         int L = nxt[i - k];
 74         if ( i + L < p + 1 ) extend[i] = L;
 75         else {
 76             j = max ( 0, p - i + 1 );
 77             while ( i + j < n && j < m && y[i + j] == x[j] ) j++;
 78             extend[i] = j;
 79             k = i;
 80         }
 81     }
 82     for ( int i = 0 ; i < n ; i++ )
 83         vis[flag][_L + i] = ( i + extend[i] == n );
 84 }
 85 
 86 struct Trie {
 87     int ch[maxn][26], val[maxn], ed[maxn];
 88     int sz;
 89     void init() {
 90         memset ( ch[0], 0, sizeof ( ch[0] ) );
 91         sz = 0, val[0] = 0, ed[0] = 0;
 92     }
 93     void add ( char *s, int n, int L ) {
 94         int u = 0;
 95         for ( int i = 0; i < n; i++ ) {
 96             int id = s[i] - ‘a‘;
 97             val[u] += vis[0][L + i];
 98             if ( !ch[u][id] ) {
 99                 ch[u][id] = ++sz;
100                 memset ( ch[sz], 0, sizeof ( ch[sz] ) );
101                 val[sz] = 0;
102                 ed[sz] = 0;
103             }
104             u = ch[u][id];
105         }
106         ed[u]++;
107     }
108     int find ( char *s, int n, int L ) {
109         int u = 0, ret = 0;
110         for ( int i = 0; i < n; i++ ) {
111             int id = s[i] - ‘a‘;
112             u = ch[u][id];
113             if ( !u ) break;
114             if ( ( i < n - 1 && vis[1][L + i + 1] ) || i == n - 1 )
115                 ret += ed[u];
116         }
117         if ( u ) ret += val[u];
118         return  ret;
119     }
120 } trie;
121 int n;
122 int main() {
123     while ( ~sf ( n ) ) {
124         mem ( vis, 0 );
125         trie.init();
126         int tot = 0;
127         for ( int i = 0; i < n ; i++ ) {
128             scanf ( "%d%s", &len[i], s + tot );
129             memcpy ( t + tot, s + tot, len[i] );
130             reverse ( t + tot, t + tot + len[i] );
131             EKMP ( t + tot, len[i], s + tot, len[i], nxt, extend, tot, 0 );
132             EKMP ( s + tot, len[i], t + tot, len[i], nxt, extend, tot, 1 );
133             trie.add ( s + tot, len[i], tot );
134             tot += len[i];
135         }
136         LL ans = 0;
137         tot = 0;
138         for ( int i = 0 ; i < n ; i++ ) {
139             ans += trie.find ( t + tot, len[i], tot );
140             tot += len[i];
141         }
142         printf ( "%lld\n", ans );
143     }
144     return 0;
145 }

View Code