WTRC's Memory

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define oo (1<<29)
#define mk(a,b) make_pair(a,b)
#define fr first
#define sc second
using namespace std;
inline int IN(){
	int x=0,ch=getchar(),f=1;
	while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
	if (ch=='-'){f=-1;ch=getchar();}
	while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}
inline void Out(ll x){
	if (x<0) putchar('-'),x=-x;
	if (x>=10) Out(x/10),putchar(x%10+'0');
		else putchar(x+'0');
}
const int N=300005;
char s[N];
int last,Cnt,n,L;
struct PAM{
	int len,num,next[26],fail;
}a[N];
void Clear(){
	Rep(i,0,N){
		a[i].len=a[i].num=a[i].fail=0;
		Rep(j,0,25) a[i].next[j]=0;
	}
}
int GetFail(int now){
	while (s[n]!=s[n-a[now].len-1]) now=a[now].fail;
	return now;
}
void Extend(int ch){
	ch-='a';
	int now=GetFail(last);
	if (!a[now].next[ch]){
		a[++Cnt].len=a[now].len+2;
		a[Cnt].fail=a[GetFail(a[now].fail)].next[ch];
		a[now].next[ch]=Cnt;
	}
	last=a[now].next[ch];
	a[last].num++;
}
ll Ans=0;
void Count(){
	Drp(i,Cnt,1){
		a[a[i].fail].num+=a[i].num;
		Ans=max(Ans,1ll*a[i].num*a[i].len);
	}
}
int main(){
	scanf("%s",s+1);L=strlen(s+1);
	Clear();
	a[1].len=-1,a[0].num=a[1].num=1,a[0].fail=a[1].fail=1;
	last=Cnt=1;
	Rep(i,1,L){n=i;Extend(s[i]);}
	Count();
	Out(Ans);
}

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define oo (1<<29)
#define mk(a,b) make_pair(a,b)
#define fr first
#define sc second
using namespace std;
inline int IN(){
	int x=0,ch=getchar(),f=1;
	while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
	if (ch=='-'){f=-1;ch=getchar();}
	while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}
inline void Out(ll x){
	if (x<0) putchar('-'),x=-x;
	if (x>=10) Out(x/10),putchar(x%10+'0');
		else putchar(x+'0');
}
const int N=500005;
int Cnt=0,T,n;
char s[N*2],ss[55];
struct Trie{
	Trie *next[26],*fail,*last;
	int fin;
}a[N];
void Insert(char *s){
	Trie *now=a;
	int len=strlen(s);
	Rep(i,0,len-1){
		if (!now->next[s[i]-'a']) Cnt++,now->next[s[i]-'a']=a+Cnt;
		now=now->next[s[i]-'a'];
	}
	now->fin++;
}
queue<Trie*>q;
void Build(){
	while (!q.empty()) q.pop();
	Rep(i,0,25){
		Trie *&v=a[0].next[i]; 
		if (v){
			v->fail=v->last=a;
			q.push(v);
		}
		else v=a;
	}
	while (!q.empty()){
		Trie *now=q.front();q.pop();
		Rep(i,0,25){
			Trie *&v=now->next[i];
			if (v){
				q.push(v);
				Trie *fa=now->fail;
				while (fa!=a&&!fa->next[i]) fa=fa->fail;
				v->fail=fa->next[i];
				v->last=v->fail->fin?v->fail:v->fail->last;
			}
			else v=now->fail->next[i];
		}
	}
}
int Count(char *s){
	int len=strlen(s),ret=0;
	Trie *now=a;
	Rep(i,0,len-1){
		now=now->next[s[i]-'a'];
		Trie *tmp=now->fin?now:now->last;
		while (tmp!=a){
			ret+=tmp->fin;
			tmp->fin=0;
			tmp=tmp->last;
		}
	}
	return ret;
}
int main(){
	T=IN();
	while (T--){
		memset(a,0,sizeof a);
		a[0].fail=a[0].last=a; 
		n=IN();
		Rep(i,1,n){scanf("%s",ss);Insert(ss);}
		Build();
		scanf("%s",s);
		Out(Count(s)),putchar('\n');
	}
}