HDU6208 The Dominator of Strings

最新推荐文章于 2019-10-29 09:27:27 发布

Jelly_acm

最新推荐文章于 2019-10-29 09:27:27 发布

阅读量547

点赞数

分类专栏： ----ac自动机 HDU

本文链接：https://blog.csdn.net/Jelly_acm/article/details/78024429

版权

HDU 同时被 2 个专栏收录

181 篇文章

订阅专栏

----ac自动机

4 篇文章

订阅专栏

The Dominator of Strings

Time Limit: 3000/3000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 2044 Accepted Submission(s): 738

Problem Description

Here you have a set of strings. A dominator is a string of the set dominating all strings else. The string

S is dominated by

T if

S is a substring of

T .

Input

The input contains several test cases and the first line provides the total number of cases.
For each test case, the first line contains an integer

N indicating the size of the set.
Each of the following

N lines describes a string of the set in lowercase.
The total length of strings in each case has the limit of

100000 .
The limit is 30MB for the input file.

Output

For each test case, output a dominator if exist, or No if not.

Sample Input

  
  
   
   3
10
you
better
worse
richer
poorer
sickness
health
death
faithfulness
youbemyweddedwifebetterworsericherpoorersicknesshealthtilldeathdouspartandpledgeyoumyfaithfulness
5
abc
cde
abcde
abcde
bcde
3
aaaaa
aaaab
aaaac

Sample Output

  
  
   
   youbemyweddedwifebetterworsericherpoorersicknesshealthtilldeathdouspartandpledgeyoumyfaithfulness
abcde
No

——————————————————————————————————

题目的意思是给出若干个串，判断是否能找出一个串，所有串都是它的字串

思路：AC自动机，首先这个串一定是最长的，所以我们记录下当前最长串，如果处理的串比最长串长那么把之前的最长串扔到字典树里，更新最长串；如果一样长先标记下，如果之后于到更长的的标记清空，最后判标记是否还在，记录重复；否则就把当前串扔到字典树里，最后跑一边AC自动机

#include<bits/stdc++.h>

using namespace std;
const int maxn=100005;

struct Trie
{
    int next[maxn][26],fail[maxn],end[maxn];
    int root,L;
    int newnode()
    {
        memset(next[L],-1,sizeof next[L]);
        end[L++] = 0;
        return L-1;
    }
    void init()
    {
        L = 0;
        root = newnode();
    }
    void insert(char buf[])
    {
        int len = strlen(buf);
        int now = root;
        for(int i = 0; i < len; i++)
        {
            if(next[now][buf[i]-'a'] == -1)
                next[now][buf[i]-'a'] = newnode();
            now = next[now][buf[i]-'a'];
        }
        end[now]++;
    }

    bool findintree(char buf[])
    {
        int len =strlen(buf);
        int now=root;
        int flag=0;
        for(int i=0; i<len; i++)
        {
            if(next[now][buf[i]-'a']!=-1)
            {
                flag=1;
                break;
            }
            now=next[now][buf[i]-'a'];
        }
         return end[now]&&!flag;
    }



void build()
{
    queue<int>Q;
    fail[root] = root;
    for(int i = 0; i < 26; i++)
        if(next[root][i] == -1)
            next[root][i] = root;
        else
        {
            fail[next[root][i]] = root;
            Q.push(next[root][i]);
        }
    while( !Q.empty() )
    {
        int now = Q.front();
        Q.pop();
        for(int i = 0; i < 26; i++)
            if(next[now][i] == -1)
                next[now][i] = next[fail[now]][i];
            else
            {
                fail[next[now][i]]=next[fail[now]][i];
                Q.push(next[now][i]);
            }
    }
}
int query(char buf[])
{
    int len = strlen(buf);
    int now = root;
    int res = 0;
    for(int i = 0; i < len; i++)
    {
        now = next[now][buf[i]-'a'];
        int temp = now;
        while( temp != root )
        {
            res += end[temp];
            end[temp] = 0;
            temp = fail[temp];
        }
    }
    return res;
}
void debug()
{
    printf("id =    ,fail =    ,end =    ,chi = [ a b c d e f g h i j k l m n o p q r s t u v w x y z]\n");
    for(int i = 0; i < L; i++)
    {
        printf("id = %3d,fail = %3d,end = %3d,chi = [",i,fail[i],end[i]);
        for(int j = 0; j < 26; j++)
            printf("%2d",next[i][j]);
        printf("]\n");
    }
}
}ac;
char dic[100005],str[100005];
int main()
{
    int t,n;
    scanf("%d",&t);
    while(t--)
    {
    int flag=0;
        str[0]='\0';
        ac.init();
        scanf("%d",&n);
        int kk=1;
       for(int i=0;i<n;i++)
        {
            scanf("%s",dic);
            if(strlen(dic)>strlen(str))
            {
                flag=0;
                if(str[0]!='\0')
                ac.insert(str);
                strcpy(str,dic);
            }
            else if(strlen(dic)==strlen(str))
            {
                if(strcmp(dic,str)!=0)
                {
                    flag=1;
                    ac.insert(dic);
                }
                else
                kk++;
            }
            else
            ac.insert(dic);
        }
        ac.build();
        int ans=ac.query(str);
        if(flag) printf("No\n");
        else
        printf("%s\n",ans==n-kk?str:"No");
    }
    return 0;
}