UVAlive 7041 The Problem to Slow Down You(回文树)

题目链接:

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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Golang语言社区

go interface

Go不是一种典型的OO语言,它在语法上不支持类和继承的概念。 没有继承是否就无法拥有多态行为了呢?答案是否定的,Go语言引入了一种新类型—Interface,它...

3245
来自专栏专注数据中心高性能网络技术研发

[Effective Modern C++(11&14)]Chapter 3: Moving to Modern C++

2286
来自专栏python3

python for循环

当range执行完之后,代码执行else部分代码。如果遇到break,终止循环,不会走else代码

1451
来自专栏大闲人柴毛毛

深入理解java异常处理机制

 1. 引子        try…catch…finally恐怕是大家再熟悉不过的语句了,而且感觉用起来也是很简单,逻辑上似乎也是很容易理解。不过,...

2364
来自专栏码云1024

c++自定义类型

3126
来自专栏Java技术栈

Java中的宏变量,宏替换详解。

群友在微信群讨论的一个话题,有点意思,特拿出来分享一下。 ? 输出true false 来看下面这段程序,和群友分享的大致一样。 public static ...

4225
来自专栏用户2442861的专栏

深入理解java异常处理机制

http://blog.csdn.net/hguisu/article/details/6155636

822
来自专栏Golang语言社区

深入分析golang多值返回以及闭包的实现

一、前言 golang有很多新颖的特性,不知道大家的使用的时候,有没想过,这些特性是如何实现的?当然你可能会说,不了解这些特性好像也不影响自己使用golang,...

4756
来自专栏Java3y

泛型就这么简单

1614
来自专栏java 成神之路

JAVA对象在JVM中内存分配

34512

扫码关注云+社区

领取腾讯云代金券