HDU 6138 Fleet of the Eternal Throne ( AC自动机)

HDU 6138 Fleet of the Eternal Throne ( AC自动机)FleetoftheEternalThroneTimeLimit:2000/1000MS(Java/Others)    MemoryLimit:65536/65536K(Java/Others)TotalSubmission(s):291    AcceptedSubmission(s):131ProblemDescription

大家好,又见面了,我是你们的朋友全栈君。

Fleet of the Eternal Throne

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 291    Accepted Submission(s): 131




Problem Description
> The Eternal Fleet was built many centuries ago before the time of Valkorion by an unknown race on the planet of Iokath. The fate of the Fleet’s builders is unknown but their legacy would live on. Its first known action was in the annihilation of all life in Wild Space. It spread across Wild Space and conquered almost every inhabited world within the region, including Zakuul. They were finally defeated by a mysterious vessel known as the Gravestone, a massive alien warship that countered the Eternal Fleet’s might. Outfitted with specialized weapons designed to take out multiple targets at once, the Gravestone destroyed whole sections of the fleet with a single shot. The Eternal Fleet was finally defeated over Zakuul, where it was deactivated and hidden away. The Gravestone landed in the swamps of Zakuul, where the crew scuttled it and hid it away.

>

> — Wookieepedia

The major defeat of the Eternal Fleet is the connected defensive network. Though being effective in defensing a large fleet, it finally led to a chain-reaction and was destroyed by the Gravestone. Therefore, when the next generation of Eternal Fleet is built, you are asked to check the risk of the chain reaction.

The battleships of the Eternal Fleet are placed on a 2D plane of 

n  rows. Each row is an array of battleships. The type of a battleship is denoted by an English lowercase alphabet. In other words, each row can be treated as a string. Below lists a possible configuration of the Eternal Fleet.

aa

bbbaaa

abbaababa

abba

If in the 

x -th row and the 

y -th row, there exists a consecutive segment of battleships that looks identical in both rows (i.e., a common substring of the 

x -th row and 

y -th row), at the same time the substring is a prefix of any other row (can be the 

x -th or the 

y -th row), the Eternal Fleet will have a risk of causing chain reaction.

Given a query (

x

y ), you should find the longest substring that have a risk of causing chain reaction.

 


Input
The first line of the input contains an integer 

T , denoting the number of test cases. 

For each test cases, the first line contains integer 

n  (

n105 ).

There are 

n  lines following, each has a string consisting of lower case letters denoting the battleships in the row. The total length of the strings will not exceed 

105 .

And an integer 

m  (

1m100 ) is following, representing the number of queries. 

For each of the following 

m  lines, there are two integers 

x,y , denoting the query.

 


Output
You should output the answers for the queries, one integer per line.
 


Sample Input
  
  
  
1 3 aaa baaa caaa 2 2 3 1 2
 


Sample Output
  
  
  
3 3
 


Source
 


Recommend
liuyiding   |   We have carefully selected several similar problems for you:  
6143 
6142 
6141 
6140 
6139 

题解:对n个串造出 自动AC机 ,这里的AC机不需要维护单词的结束点  需要维护一个每个节点到根的距离,也就是前缀的长度。然后用x跑一遍AC机,在所有匹配成功的结束节点上记上一个标记(直接记成询问次数就行了:第一次询问flag记成1,第二次记成2,这样保证每次的flag都不一样就不用清空标记了),然后这些标记点的意思就是:这个前缀是n个串中某个的前缀,且这个前缀是串x的字串。然后再用y跑一次AC机,在y匹配成功的节点,如果他刚刚被打了标记,那就统计最长的length就可以。对于每个节点都要打标记,不是在字母最后一个地方打。。


原来模板太不好变化了。。有改了下

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 1e6 + 7;
const int maxnode = 50*10010;
int n;
char s1[60], s2[maxn];
int pos[maxn];
struct node
{
    int ch[maxnode][26], cnt[maxnode], fail[maxnode], last[maxnode], id, road[maxnode]; // 路径压缩优化, 针对模式串出线的种类
    int dep[maxnode], flag[maxnode];
    void init()
    {
        memset(ch[0], 0, sizeof(ch[0]));
        memset(dep, 0, sizeof(dep));
        id = 1;
    }
    void Insert(char *s)
    {
        int rt = 0;
        int len = strlen(s);
        dep[rt] = 0;
        for(int i = 0; i < len; i++)
        {
            if(!ch[rt][s[i]-'a'])
            {
                memset(ch[id], 0, sizeof(ch[id]));
                flag[id] = 0;
                ch[rt][s[i]-'a'] = id++;
            }
            dep[ch[rt][s[i]-'a']] = dep[rt] + 1;
            rt = ch[rt][s[i]-'a'];
        }
    }
    void get_fail()
    {
        queue<int> q;
        fail[0] = 0;
        int rt = 0;
        for(int i = 0; i < 26; i++)
        {
            rt = ch[0][i];
            if(rt)
            {
                q.push(rt);
                fail[rt] = 0;
            }
        }
        while(!q.empty())
        {
            int r = q.front();
            q.pop();
            for(int i = 0; i < 26; i++)
            {
                rt = ch[r][i];
                if(!rt)
                {
                    ch[r][i] = ch[fail[r]][i];
                    continue;
                }
                q.push(rt);
                fail[ch[r][i]] = ch[fail[r]][i];
            }
        }
    }
    void Match(char *s, int f)
    {
        int rt = 0;
        int len = strlen(s);
        for(int i = 0; i < len; i++)
        {
            int temp = rt = ch[rt][s[i]-'a'];
            while(temp)
            {
                flag[temp] = f;
                temp = fail[temp];
            }
        }
    }
    int Search(char *s, int f)
    {
        int rt = 0, res = 0;
        int len = strlen(s);
        for(int i = 0; i < len; i++)
        {
            int temp = rt = ch[rt][s[i]-'a'];
            while(temp)
            {
                if(flag[temp] == f) res = max(res, dep[temp]);
                temp = fail[temp];
            }
        }
        return res;
    }
}ac_auto;
char s[maxn];
int main()
{
    int t, q;
    cin >> t;
    while(t--)
    {
        scanf("%d", &n);
        int d = 0;
        ac_auto.init();
        for(int i = 0; i < n; i++)
        {
            pos[i] = d;
            scanf(" %s", s+d);
            ac_auto.Insert(s+d);
            int len = strlen(s+d);
            d += len + 1;
        }
        ac_auto.get_fail();
        scanf("%d", &q);
        int ca = 1;
        while(q--)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            x--; y--;
            ac_auto.Match(s+pos[x],ca);
            int ans = ac_auto.Search(s+pos[y], ca++);
            printf("%d\n", ans);
        }
    }
    return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/138514.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 喜报!盛讯美恒USBserver收到百度云邀请 正式入驻百度云市场

    喜报!盛讯美恒USBserver收到百度云邀请 正式入驻百度云市场

  • spring解析自定义注解_事务的注解@Transactional的属性

    spring解析自定义注解_事务的注解@Transactional的属性前言众所周知,spring从2.5版本以后开始支持使用注解代替繁琐的xml配置,到了springboot更是全面拥抱了注解式配置。平时在使用的时候,点开一些常见的等注解,会发现往往在一

  • raid 5 raid 10_u盘损坏了还能恢复吗

    raid 5 raid 10_u盘损坏了还能恢复吗介绍:RAID0技术把多块物理硬盘设备(至少两块)通过硬件或软件的方式串联在一起,组成一个大的卷组,并将数据依次写入到各个物理硬盘中。这样一来,在最理想的状态下,硬盘设备的读写性能会提升数倍

  • bridge桥接模式_透明桥模式

    bridge桥接模式_透明桥模式bridge模式动机案例要点总结笔记动机由于某些类型的固有的实现逻辑,使得他们具有两个变化维度,乃至多个维度的变换如何应对这种”多维度的变化“?如何利用面向对象技术来是使得类型可以轻松地沿着两个乃至多个方向变换而不引入额外地复杂度?案例PC端和Mobile端平台和业务分离朴素class Messager{ public: virtual void Login(string username,string password) = 0; virtual void SendM

  • C# 远程唤醒(远程开机)

    C# 远程唤醒(远程开机)C#远程唤醒(远程开机)近日,小白要用到远程开机的功能,网上大多介绍的是MagicPacket的工具。实际上,此MagicPacket是AMD公司开发的,请在google.cn中搜索MagicPacketTechnology。原理上我们不用深入,实现上是发一个BroadCast包,包的内容包括以下数据就可以了。FFFFFFFFFFFF,6个FF是数据的开始,紧跟着16次

  • 数据仓库之电商数仓– 3.1、电商数据仓库系统(ODS层、DIM层、DWD层)

    数据仓库之电商数仓– 3.1、电商数据仓库系统(ODS层、DIM层、DWD层)目录一、数仓分层1.1为什么要分层1.2数据集市与数据仓库概念1.3数仓命名规范1.3.1表命名1.3.2脚本命名1.3.3表字段类型二、数仓理论2.1范式理论2.1.1范式概念2.1.2函数依赖2.1.3三范式区分2.2关系建模与维度建模2.2.1关系建模2.2.2维度建模⭐️2.3维度表和事实表⭐️2.3.1维度表2.3.2事实表2.4维度模型分类2.5数据仓库建模⭐️????2.5.1ODS层2.5.2DIM层和DWD层2.5.3DWS层与DWT层2.5.4

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号