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)


相关推荐

  • 在一台2010年的老电脑上安装黑群辉dsm5.2并完成外网访问与洗白操作

    在一台2010年的老电脑上安装黑群辉dsm5.2并完成外网访问与洗白操作背景我和媳妇的手机容量都快要满了,主要是手机存储了大量的照片和视频,所以考虑个解决方案给手机瘦身。方案要满足一下几个要求:1、数据非常重要,一定要保证数据的可靠性;2、自动完成照片的比较,然后上传;3、照片需要满足随时、随地查看;4、保证数据的安全及私密性,最好不使用公共网盘服务(怕开发商做恶)5、总投入费用不超过300块钱。方案对比方案1(最优雅):使用手机厂商自带的云存储服务,以appleicloud为例,50G的存储已经不够用了,需要升级到200G的方案,一个月就是21块钱,一年是252

  • Java面试题–较经典

    Java面试题–较经典1、出处:2016年360Java面试题:原题:首先 代码跑一边 保证正确性。分析:往方法中传参,传的仅仅只是地址,而不是实际内存,所以不要以为y=x程序的执行,是 b=a的执行。这两者是不相等的。 2、出处:2016年 阿里巴巴Java面试题:原题:分析:本题是一个自动拆装箱的考题(自动拆装箱JDK需在1.5上)参考:https://blog….

  • Java爬取先知论坛文章

    Java爬取先知论坛文章0x00前言上篇文章写了部分爬虫代码,这里给出一个完整的爬取先知论坛文章代码,用于技术交流。0x01代码实现pom.xml加入依赖:<dependencie

    2021年12月12日
  • 常见的反爬虫和应对方法「建议收藏」

    常见的反爬虫和应对方法「建议收藏」常见的反爬虫和应对方法

  • 科学计数法E表示什么_科学计数法e-5什么意思

    科学计数法E表示什么_科学计数法e-5什么意思计算机表达10的幂是一般是用E或e,即1.03乘10的8次方,可简写为“1.03E+08”的形式-1.03乘10的8次方,可简写为“-1.03E+08”的形式1.03乘10的-8次方,可简写为“1.03E-08”的形式-1.03乘10的-8次方,可简写为“-1.03E-08”的形式…

    2022年10月23日
  • Fleet究竟是什么?为什么最近这么火~

    Fleet究竟是什么?为什么最近这么火~如何看待JetBrains推出的轻量级编辑器Fleet?

发表回复

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

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