本文共 4343 字，大约阅读时间需要 14 分钟。
题意：
给你n个串串，每个串串可以选择和n个字符串拼接（可以自己和自己拼接），问有多少个拼接后的字符串是回文。
所有的串串长度不超过2e6；
题解：
这题由于是在POJ上，所以string也用不了，会tle。
串串个数也比较多，开不下二维的char数组，卡内存。
所以数据的预处理需要处理成一个串串，把所有的串串放在一个串里面。
记录每一个串串的起始位置和长度。
数据预处理部分就解决了。
然后就是核心思想部分了。
首先你要知道如何用EX_KMP求串串前缀和后缀是否是回文。（其实也可以用马拉车）
其实这个就是t串等于s串的反串，然后做一个EX_KMP就可以了。
不会的可以做做这一题
于是我们处理出了所有串串的前缀和后缀是否是一个回文。
下面看这个例子 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 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 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" = "< < = 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) 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 }
转载于:https://www.cnblogs.com/qldabiaoge/p/11310169.html
