题目链接:

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5053

先把第一个串插入回文树中,然后把s数组清空插入第二个串,统计两个cnt数组,答案是二者相乘的结果

#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <string.h> using namespace std;
typedef long long int LL;
const int maxn=2e5+5;
char str1[maxn];
char str2[maxn];
int n;
LL ans;
struct Tree
{
const static int maxn=4e5+5;
int next[maxn][26];
int fail[maxn];
LL cnt[maxn];
LL cnt2[maxn];
int len[maxn];
int s[maxn];
int last,p,n;
int new_node(int x)
{
memset(next[p],0,sizeof(next[p]));
cnt[p]=0;
cnt2[p]=0;
len[p]=x;
return p++;
}
void init()
{
//memset(cnt,0,sizeof(cnt));
//memset(cnt2,0,sizeof(cnt2));
p=0;
new_node(0);
new_node(-1);
last=0;
n=0;
s[0]=-1;
fail[0]=1;
}
void init2()
{
last=0;
s[0]=-1;
fail[0]=1;
n=0;
}
int get_fail(int x)
{
while(s[n-len[x]-1]!=s[n])
x=fail[x];
return x;
}
void add(int x)
{
x-='a';
s[++n]=x;
int cur=get_fail(last);
if(!(last=next[cur][x]))
{
int now=new_node(len[cur]+2);
fail[now]=next[get_fail(fail[cur])][x];
next[cur][x]=now;
last=now;
}
cnt[last]++;
}
void add2(int x)
{
x-='a';
s[++n]=x;
int cur=get_fail(last);
if(!(last=next[cur][x]))
{
int now=new_node(len[cur]+2);
fail[now]=next[get_fail(fail[cur])][x];
next[cur][x]=now;
last=now;
}
cnt2[last]++;
} void count()
{
for(int i=p-1;i>=0;i--)
cnt[fail[i]]+=cnt[i];
}
void count2()
{
for(int i=p-1;i>=0;i--)
cnt2[fail[i]]+=cnt2[i];
}
void fun()
{
for(int i=2;i<=p-1;i++)
{
ans+=cnt[i]*cnt2[i];
}
} }tree;
int main()
{
scanf("%d",&n);
for(int j=1;j<=n;j++)
{
scanf("%s%s",str1,str2);
tree.init();
int len=strlen(str1);
int len1=strlen(str2);
for(int i=0;i<len;i++)
{
tree.add(str1[i]);
}
tree.count();
tree.init2();
ans=0;
for(int i=0;i<len1;i++)
{
tree.add2(str2[i]);
}
tree.count2();
tree.fun();
printf("Case #%d: %lld\n",j,ans);
}
return 0;
}

最新文章

  1. jmap之使用说明与JVM配置
  2. 多线程获取不到HttpContext
  3. 使用IConfigurationSectionHandler在web.config中增加自定义配置
  4. linux使用脚本自动连接数据库
  5. 百度编辑器Ueditor的简单调用
  6. Android 中使用自定义字体的方法
  7. windows内核初窥(二)-----系统机制
  8. C++之函数指针
  9. POJ 3481 Double Queue STLmap和set新学到的一点用法
  10. Delphi的VMT的结构图,很清楚
  11. 经典算法题每日演练——第七题 KMP算法
  12. 显示linux开机时间的脚本
  13. Json填充到Form中
  14. 【VB超简单入门】六、基本数据类型
  15. Spark Core
  16. [PHP] 链表数据结构(单链表)
  17. 初识gispro
  18. JQuery攻略(五)表单验证
  19. 一个将java事物的非常好的栗子
  20. Django_信号

热门文章

  1. angular过滤器使用 自定义过滤器
  2. Ajax高级应用---Comet
  3. OSGi规范概要
  4. cocos2d-JS (二)Cocos Creater
  5. 简单的异步Socket实现——SimpleSocket_V1.1
  6. how to identify your .NET Framework version
  7. AppStore苹果应用支付开发(In App Purchase)翻译
  8. hdu6055 Regular polygon 脑洞几何 给定n个坐标(x,y)。x,y都是整数,求有多少个正多边形。因为点都是整数点,所以只可能是正四边形。
  9. Unity3D脚本:C#计时类脚本
  10. php 怎么查看是否开启了socket