POJ3376 Finding Palindromes

知识点：Trie树（字典树）、拓展kmp（manacher？）、时间空间复杂度

题目

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.

样例

输入

3
1 a
2 ab
2 ba

输出

提示

The 5 palindromes are:
aa aba aba abba baab

题意

n个字符串构成一个数组，求以这个数组为行和列，行上的一个字符串与列上的一个字符串有序连接构成的n*n的矩阵中回文串有多少个。

思路

这是我的提交

原来习惯性的开longlong这次被卡MLE了，并且是mana数组改成bool后才过的，平时开内存很大方的建议这次收敛一点。
这题manacher判断回文估计也可以，这里使用拓展kmp算法求回文长度。
对任意两个字符串，模拟一遍可以发现，若能够成回文串，
1、两个字符串长度相同且对称
2、短字符串与长字符串的部分对称，剩余部分为回文串，转换为短字符串的逆序串与长字符串的前缀或后缀相同，剩余部分为回文串，进一步转换为：长+短的逆，长字符串的前缀和短字符串相同，后缀为回文串。
后缀回文串只对主串而言，且有多个，可以开辟内存存储每个字符串的后缀回文串。前缀需要和短逆字符串匹配，可以使用kmp算法，但每次都需要两两匹配，O（n^2），又因为求前缀的特性，想到Trie字典树，可以用来处理前缀信息，且插入和查询的复杂度为O（n），故使用Trie树存储每个字符串，再用逆字符串匹配，每次前缀匹配成功的时候将从最后匹配位置开始的所有回文后缀的贡献（已存到字符串对应位置中）加到答案里。
需要注意的一点，当待匹配逆字符串短于Trie树中的字符串，应从Trie树中取得后缀的贡献，待匹配逆字符串长于Trie树中的字符串，应从逆字符串中取得后缀的贡献。
实现思路见代码。

代码

#include"cstdio"
#include"cstring"
#include"algorithm"
#define ll int
#define min(a,b) (a<b?a:b)
#define max(a,b) (a<b?b:a)
const int N=2e6+3;
//卡MLE和TLE，使用char数组存储输入的字符串，并首尾相连
char str[2][N];//str[0]：正序字符串，str[1]：逆序字符串
//mana[][i];i位置开始的后缀是否为回文串，同分正逆序
bool mana[2][N];
//kmp的next数组和extend数组
//st[i]：每个字符串的开始位置在数组中的位置为i且长度为st[i]
ll nxt[N],ext[N],st[N];
//快读
inline ll read() {
   
  ll v=0,f=1;
  char c=getchar();
  while(c<'0'||c>'9') {
   
    if(c=='-') f=-1;
    if((c=getchar())==EOF) return EOF;
  }
  while(c>='0'&&c<='9') {
   
    v=v*10+c-'0';
    c=getchar();
  }
  return v*f;
}

struct node {
   
  //cnt：以i节点结束的字符串数量，mana：以i节点开始的回文串数量，nxt：孩子节点
  ll cnt,mana,nxt[26];
} trie[N];
//节点数量（从1开始）
ll cont;
//正逆标志为f的字符数组left到right（左闭右开）求next数组
inline void prekmp(ll left,ll right,bool f) {
   
  nxt[left]=right-left;
  for(ll i=left+1,l=left,r=left; i<right; ++i) {
   
    if(i+nxt[i-l+left]>=r) {
   
      if(i>r) r=i;
      while(r<right&&str[f][r]==str[f][r-i+left]) ++r;
      nxt[i]=r-i;
      l=i;
    } else nxt[i]=nxt[i-l+left];
  }
}
//正逆标志为f的字符数组left到right（左闭右开）对与自己对称的字符串求extend数组
inline void kmp(ll left,ll right,bool f) {
   
  prekmp(left,right,!f);//求与自己对称的字符串的next数组
  for(ll i=left,l=left,r=left; i<right; ++i) {
   
    if(i+nxt[i-l+left]>=r) {
   
      if(i>r) r=i;
      while(r<right&&str[f][r]==str[!f][r-i+left]) ++r;
      ext[i]=r-i;
      l=i;
    } else ext[i]=nxt[i-l+left];
  }
}
//正序字符数组l到r（左闭右开）插入Trie树
inline void insert(ll l,ll r) {
   
  ll p=0;
  for(ll i=l; i<r; ++i) {
   
    ll &to=trie[p].nxt[str[0][i]-'a'];
    if(to) p=to;
    else {
   
      p=to=++cont;
      memset(trie+p,0,sizeof trie[p]);
    }
    //插入i位置后，i不是最后一个字符且i的后一位开始的后缀是回文
    if(i!=r-1&&mana[0][i+1]) ++trie[p].mana;
  }
  ++trie[p].cnt;
}
//逆序字符数组l到r（左闭右开）匹配Trie树
inline ll query(ll l,ll r) {
   
  ll p=0,ans=0;
  for(ll i=l; i<r; ++i) {
   
    ll &to=trie[p].nxt[str[1][i]-'a'];
    if(to) {
   
      p=to;
      //i位置匹配成功后，Trie树中的字符串有达到了结束位置且（i是最后一个字符（长度相同的匹配）或i后一位开始的后缀是回文串（逆序串长，Trie树中的正序串短））
      if(trie[p].cnt&&(i==r-1||mana[1][i+1])) ans+=trie[p].cnt;
    } else return ans;//匹配失败直接返回（好像不可能）
  }
  //逆序串匹配结束Trie树中的位置p，逆序串短，Trie树中的正序串长
  ans+=trie[p].mana;
  return ans;
}

inline void init(ll len) {
   
  memset(mana,0,sizeof mana);
  memset(trie,0,sizeof trie[0]);
  cont=0;
}

int main() {
   
  ll n;
  while((n=read())!=EOF) {
   
    ll p=0;
    memset(st,0,sizeof st);
    for(ll i=0; i<n; ++i) {
   
      ll len=read();
      ll r=p+len;
      for(ll i=p; i<r; ++i) str[0][i]=getchar();
      //生成逆串
      memcpy(str[1]+p,str[0]+p,len);
      std::reverse(str[1]+p,str[1]+r);
      st[p]=len;
      p+=len;
    }
    init(p);
    //类似链表的遍历
    //记录后缀回文串
    for(ll i=0; i!=p; i+=st[i]) {
   
      ll r=i+st[i];
      //一次求正序串后缀回文串，一次求逆序
      for(ll j=0; j<2; ++j) {
   
        kmp(i,r,j);
        for(ll k=i+1; k<r; ++k)//字符串开始位置不算后缀，从字符串开始位置后一位算起
          if(k+ext[k]==r) mana[j][k]=true;
      }
    }
    //插入正序字符串
    for(ll i=0; i!=p; i+=st[i])
      insert(i,i+st[i]);
    //匹配逆序字符串
    long long ans=0;
    for(ll i=0; i!=p; i+=st[i])
      ans+=query(i,i+st[i]);
    printf("%lld\n",ans);
  }
  return 0;
}