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]。

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

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

 #include <cstdio>

 #include <cstring>

 #include <queue>

 #include <cmath>

 #include <algorithm>

 #include <set>

 #include <iostream>

 #include <map>

 #include <stack>

 #include <string>

 #include <time.h>

 #include <vector>

 #define  pi acos(-1.0)

 #define  eps 1e-9

 #define  fi first

 #define  se second

 #define  rtl   rt<<1

 #define  rtr   rt<<1|1

 #define  bug         printf("******\n")

 #define  mem(a,b)    memset(a,b,sizeof(a))

 #define  name2str(x) #x

 #define  fuck(x)     cout<<#x" = "<<x<<endl

 #define  f(a)        a*a

 #define  sf(n)       scanf("%d", &n)

 #define  sff(a,b)    scanf("%d %d", &a, &b)

 #define  sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)

 #define  sffff(a,b,c,d) scanf("%d %d %d %d", &a, &b, &c, &d)

 #define  pf          printf

 #define  FRE(i,a,b)  for(i = a; i <= b; i++)

 #define  FREE(i,a,b) for(i = a; i >= b; i--)

 #define  FRL(i,a,b)  for(i = a; i < b; i++)+

 #define  FRLL(i,a,b) for(i = a; i > b; i--)

 #define  FIN         freopen("data.txt","r",stdin)

 #define  gcd(a,b)    __gcd(a,b)

 #define  lowbit(x)   x&-x

 #define rep(i,a,b) for(int i=a;i<b;++i)

 #define per(i,a,b) for(int i=a-1;i>=b;--i)

 using namespace std;

 typedef long long  LL;

 typedef unsigned long long ULL;

 const int maxn = 2e6 + ;

 const int maxm = 8e6 + ;

 const int INF = 0x3f3f3f3f;

 const int mod = ;

 int nxt[maxn], extend[maxn], len[maxn], vis[][maxn];

 char s[maxn], t[maxn];

 void pre_EKMP ( char x[], int m, int nxt[] ) {

     nxt[] = m;

     int j = ;

     while ( j +  < m && x[j] == x[j + ] ) j++;

     nxt[] = j;

     int k = ;

     for ( int i = ; i < m; i++ ) {

         int p = nxt[k] + k - ;

         int L = nxt[i - k];

         if ( i + L < p +  ) nxt[i] = L;

         else {

             j = max ( , p - i +  );

             while ( i + j < m && x[i + j] == x[j] ) j++;

             nxt[i] = j;

             k = i;

         }

     }

 }

 void EKMP ( char x[], int m, char y[], int n, int nxt[], int extend[], int _L, int flag ) {

     pre_EKMP ( x, m, nxt );

     int j = ;

     while ( j < n && j < m && x[j] == y[j] ) j++;

     extend[] = j;

     int k = ;

     for ( int i = ; i < n; i++ ) {

         int p = extend[k] + k - ;

         int L = nxt[i - k];

         if ( i + L < p +  ) extend[i] = L;

         else {

             j = max ( , p - i +  );

             while ( i + j < n && j < m && y[i + j] == x[j] ) j++;

             extend[i] = j;

             k = i;

         }

     }

     for ( int i =  ; i < n ; i++ )

         vis[flag][_L + i] = ( i + extend[i] == n );

 }

 struct Trie {

     int ch[maxn][], val[maxn], ed[maxn];

     int sz;

     void init() {

         memset ( ch[], , sizeof ( ch[] ) );

         sz = , val[] = , ed[] = ;

     }

     void add ( char *s, int n, int L ) {

         int u = ;

         for ( int i = ; i < n; i++ ) {

             int id = s[i] - 'a';

             val[u] += vis[][L + i];

             if ( !ch[u][id] ) {

                 ch[u][id] = ++sz;

                 memset ( ch[sz], , sizeof ( ch[sz] ) );

                 val[sz] = ;

                 ed[sz] = ;

             }

             u = ch[u][id];

         }

         ed[u]++;

     }

     int find ( char *s, int n, int L ) {

         int u = , ret = ;

         for ( int i = ; i < n; i++ ) {

             int id = s[i] - 'a';

             u = ch[u][id];

             if ( !u ) break;

             if ( ( i < n -  && vis[][L + i + ] ) || i == n -  )

                 ret += ed[u];

         }

         if ( u ) ret += val[u];

         return  ret;

     }

 } trie;

 int n;

 int main() {

     while ( ~sf ( n ) ) {

         mem ( vis,  );

         trie.init();

         int tot = ;

         for ( int i = ; i < n ; i++ ) {

             scanf ( "%d%s", &len[i], s + tot );

             memcpy ( t + tot, s + tot, len[i] );

             reverse ( t + tot, t + tot + len[i] );

             EKMP ( t + tot, len[i], s + tot, len[i], nxt, extend, tot,  );

             EKMP ( s + tot, len[i], t + tot, len[i], nxt, extend, tot,  );

             trie.add ( s + tot, len[i], tot );

             tot += len[i];

         }

         LL ans = ;

         tot = ;

         for ( int i =  ; i < n ; i++ ) {

             ans += trie.find ( t + tot, len[i], tot );

             tot += len[i];

         }

         printf ( "%lld\n", ans );

     }

     return ;

 }

巴特西

POJ 3376 Finding Palindromes EX-KMP+字典树

最新文章

热门文章