UVALive 6933 Virus synthesis(回文树)

Viruses are usually bad for your health. How about ghting them with... other viruses? In this problem,

you need to nd out how to synthesize such good viruses.

We have prepared for you a set of strings of the letters A, G, T and C. They correspond to the

DNA nucleotide sequences of viruses that we want to synthesize, using the following operations:

• Adding a nucleotide either to the beginning or the end of the existing sequence.

• Replicating the sequence, reversing the copied piece, and gluing it either to the beginning or to

the end of the original (so that e.g., AGTC can become AGTCCTGA or CTGAAGTC).

We're concerned about efficiency, since we have very many such sequences, some of them very long.

Find a way to synthesize them in a minimum number of operations.

Input

The rst line of input contains the number of test cases T. The descriptions of the test cases follow:

Each test case consists of a single line containing a non-empty string. The string uses only the

capital letters `A', `C', `G' and `T' and is not longer than 100 000 characters.

Output

For each test case, output a single line containing the minimum total number of operations necessary

to construct the given sequence.

Sample Input

4

AAAA

AGCTTGCA

AAGGGGAAGGGGAA

AAACAGTCCTGACAAAAAAAAAAAAC

Sample Output

3

8

6

18

参考大牛的博客 http://www.cnblogs.com/clrs97/p/4700658.html

#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <map>


using namespace std;
typedef long long int LL;
const int maxn=1e5+5;
map<char,int> m;
int n;
char str[maxn];
int f[maxn];
struct Tree
{
    int next[maxn][4];
    int fail[maxn];
    int train[maxn];
    int len[maxn];
    int num[maxn];
    int cnt[maxn];
    int s[maxn];
    int last;
    int p;
    int n;
    int new_node(int x)
    {
        memset(next[p],0,sizeof(next[p]));
        len[p]=x;
        return p++;
    }
    void init()
    {
        p=0;
        new_node(0);
        new_node(-1);
        last=0;n=0;
        s[0]=-1;
        fail[0]=1;
    }
    int get_fail(int x)
    {
        while(s[n-len[x]-1]!=s[n])
            x=fail[x];
        return x;
    }
    int get_fail2(int x,int pos)
    {
        while(s[n-len[x]-1]!=s[n]||(len[x]+2)*2>len[pos])
            x=fail[x];
        return x;
    }
    void add(char xx)
    {
        int x=m[xx];
        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];
			if(len[now]<=2)
				train[now]=fail[now];
			else
                train[now]=next[get_fail2(train[cur],now)][x];
            
            next[cur][x]=now;
            last=now;
        }
    }
}tree;
int ans;
int q[maxn];
int rear,head;
int main()
{
    int t;
    scanf("%d",&t);
    m['A']=0;m['C']=1;m['G']=2;m['T']=3;
    while(t--)
    {
        scanf("%s",str);
        int len=strlen(str);
        tree.init();
        ans=len;
        for(int i=0;i<len;i++)
        {
            tree.add(str[i]);
        }
        memset(f,0,sizeof(f));
        for(int i=2;i<tree.p;i++)
        {
            if(tree.len[i]&1)
                f[i]=tree.len[i];
        }
        f[0]=1;
        q[0]=0;
        head=0;rear=1;
        int x,y;
        while(head<rear)
        {
            x=q[head++];
            for(int i=0;i<4;i++)
            {
                if(tree.next[x][i])
                {
                     y=tree.next[x][i];
                    f[y]=f[x]+1;
                    f[y]=min(f[y],tree.len[y]/2-tree.len[tree.train[y]]+f[tree.train[y]]+1);
                    ans=min(ans,len-tree.len[y]+f[y]);
					q[rear++]=y;
                }
                
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏HansBug's Lab

1643: [Usaco2007 Oct]Bessie's Secret Pasture 贝茜的秘密草坪

1643: [Usaco2007 Oct]Bessie's Secret Pasture 贝茜的秘密草坪 Time Limit: 5 Sec  Memory L...

34340
来自专栏杨熹的专栏

【LEETCODE】模拟面试-134-Gas Station

新生 题目: https://leetcode.com/problems/gas-station/ There are N gas stations alon...

35560
来自专栏开发与安全

90% of python in 90 minutes

注:本文整理自 http://www.slideshare.net/MattHarrison4/learn-90 -----------------------...

23200
来自专栏算法修养

POJ-1125 Stockbroker Grapevine

Stockbroker Grapevine Time Limit: 1000MS Memory Limit: 10000K Total Sub...

31840
来自专栏函数式编程语言及工具

SDP(9):MongoDB-Scala - data access and modeling

    MongoDB是一种文件型数据库,对数据格式没有硬性要求,所以可以实现灵活多变的数据存储和读取。MongoDB又是一种分布式数据库,与传统关系数据库不同...

39640
来自专栏码匠的流水账

聊聊flink LocalEnvironment的execute方法

flink-java-1.6.2-sources.jar!/org/apache/flink/api/java/DataSet.java

21530
来自专栏HansBug's Lab

2292: 【POJ Challenge 】永远挑战

2292: 【POJ Challenge 】永远挑战 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 553 ...

30860
来自专栏算法修养

HOJ 1438 The Tower of Babylon(线性DP)

The Tower of Babylon My Tags Cancel - Seperate tags with commas. Source...

296110
来自专栏java、Spring、技术分享

深入分析Spring MVC中RequestBody与ResponseBody

  在SpringMVC中,可以使用@RequestBody和@ResponseBody两个注解,分别完成请求报文到对象和对象到响应报文的转换。在Sprin...

31310
来自专栏函数式编程语言及工具

Cats(1)- 从Free开始,Free cats

  cats是scala的一个新的函数式编程工具库,其设计原理基本继承了scalaz:大家都是haskell typeclass的scala版实现。当然,cat...

239100

扫码关注云+社区

领取腾讯云代金券