HDU 6208 The Dominator of Strings【AC自动机/kmp/Sunday算法】

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

Source

2017 ACM/ICPC Asia Regional Qingdao Online

【题意】：给n个串，问是否有一个串，包含了其他所有串。

【分析】：显然若这样的字符串存在就一定是最长的那个，然后考虑下AC自动机的入门题HDU2222，然后思路就清晰了，首先构建自动机，然后选出长度最长的一串来跑一遍自动机，统计所有字符串出现的个数，不重复统计，然后个数!=n就是No。

【代码*3】：

#include<stdio.h>

#include<string.h>

#include<queue>

#include<string>

#include<iostream>

#define maxlen 100005

using namespace std;

int n;

    int nxt[maxlen][],FAIL[maxlen],edd[maxlen],root,L;//nxt记录节点，在这里edd指针代表以当前节点为字符串尾的字符串个数

    int mark[maxlen];

    int newnode()

    {

        for(int i=;i<;i++)

            nxt[L][i]=-;//节点连接的边初始化为-1

        edd[L]=;

        mark[L]=;

        return L++;

    }

    void init()

    {

        L=;

        root=newnode();

    }    

    void insert(char buf[],int l)//trie树的建立

    {

        int now=root;

        for(int i=;i<l;i++)

        {

            if(nxt[now][buf[i]-'a']==-)nxt[now][buf[i]-'a']=newnode();

            now=nxt[now][buf[i]-'a'];

        }

        edd[now]++;

    }

    void build()//建立ac自动机

    {

        queue<int>que;

        for(int i=;i<;i++)

        {

            if(nxt[root][i]==-)nxt[root][i]=root;

            else                                 //若有连边则将节点加入队列 ，并将FAIL指针指向root

            {

                FAIL[nxt[root][i]]=root;

                que.push(nxt[root][i]);

            }

        }

        while(!que.empty())

        {

            int now=que.front();

            que.pop();

            for(int i=;i<;i++)

            {

                if(nxt[now][i]==-)            //若无连边，则将该边指向当前节点FAIL指针指向的相应字符连接的节点

                    nxt[now][i]=nxt[FAIL[now]][i];

                else                            //若有连边，则将儿子节点的FAIL指针指向当前节点FAIL指针指向相应字符接的节点

                {

                    FAIL[nxt[now][i]]=nxt[FAIL[now]][i];

                    que.push(nxt[now][i]); //加入队列继续遍历

                }

            }

        }

    }

    int query(char buf[],int l)

    {

        int now=root;

        int res=;

        for(int i=;i<l;i++)

        {

            now=nxt[now][buf[i]-'a'];

            int temp=now;

            while(temp!=root&&mark[temp]==)//根据题目要求改变形式

            {

                res+=edd[temp];

                edd[temp]=;

                mark[temp]=;

                temp=FAIL[temp];

            }

        }

        return res; //在这里返回的是匹配到的模式串的数量

    }

char buf[maxlen],ans[maxlen];

string A[maxlen];

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d",&n);

        init();

        int ma=;

        for(int i=;i<n;i++)

        {

            scanf("%s",buf);

            int l=strlen(buf);

            if(ma<l)

            {

                ma=l;

                strcpy(ans,buf);

            }

            insert(buf,l);

        }

        build();

        int sum=query(ans,ma);

        if(sum==n) puts(ans);

        else puts("No");

    }

}

AC自动机

#include <stdio.h>

#include <string.h>

char S[];

char *t[],*s;

int f[];

void getfail(char p[],int f[]) //字符串p自我匹配

{

    int len=strlen(p);

    f[]=f[]=;

    for(int i=;i<len;i++)

    {

        int j=f[i];

        while(j&&p[i]!=p[j])

            j=f[j];

        if(p[i]==p[j])

            f[i+]=j+;//多匹配到了一个字符

        else

            f[i+]=;//该字符配不上

    }

}

int find(char* T, char*P, int*f)//p去匹配字符串T

{

    int n = strlen(T), m = strlen(P);

    getfail(P, f);  //得出部分匹配表

    int j = ;  //短串的下标

    for(int i = ; i < n; i++) //长串下标

    {

        while(j && P[j] != T[i])//突然失配了

        {

            j = f[j];  //j往回退，直到0或者上一个字符相等的位置

        }

        if(P[j] == T[i])

        {

            j++;  //匹配了一个字符，j++

        }

        if(j == m)  //短串匹配到头了

        {

            return ;//i - m + 1;//返回成功匹配的起点字符位置

        }

    }

    return -;

}

int main()

{

    int T,n;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d",&n);

        int maxlen=;

        int p=;//记录最长串

        s=S;

        for(int i=;i<=n;i++)

        {

            scanf("%s",s);

            t[i]=s;

            if(strlen(s)>maxlen){

                maxlen=strlen(s);

                p=i;

            }

            s+=strlen(s)+;

        }

        int ans=;

        for(int i=;i<=n;i++)

        {

            if(find(t[p],t[i],f)==)

                ans++;

            else break;

        }

        if(ans==n)

        {

            printf("%s\n",t[p]);

        }

        else puts("No");

    }

    return ;

}

KMP

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <iostream>

#define ll long long

using namespace std;

int f[];

int T,n;

char s[];

char *t[];

void getfail(char p[]) //字符串p自我匹配

{

    int len=strlen(p);

    f[]=f[]=;

    for(int i=;i<len;i++)

    {

        int j=f[i];

        while(j&&p[i]!=p[j])

            j=f[j];

        if(p[i]==p[j])

            f[i+]=j+;//多匹配到了一个字符

        else

            f[i+]=;//该字符配不上

    }

}

int find(char* T, char*P)//p去匹配字符串T

{

    int n = strlen(T), m = strlen(P);

    getfail(P);  //得出部分匹配表

    int j = ;  //短串的下标

    for(int i = ; i < n; i++) //长串下标

    {

        while(j && P[j] != T[i])//突然失配了

        {

            j = f[j];  //j往回退，直到0或者上一个字符相等的位置

        }

        if(P[j] == T[i])

        {

            j++;  //匹配了一个字符，j++

        }

        if(j == m)  //短串匹配到头了

        {

            return ;//i - m + 1;//返回成功匹配的起点字符位置

        }

    }

    return -;

} 

int main(){

    int max_len;

    scanf("%d",&T);

    while(T--){

        scanf("%d",&n);

        max_len=;

        int tmp;

        char *qw;

        char *io=s;

        for(int i= ;i <= n;i++){

            scanf("%s",io);

            tmp=strlen(io);

            if( tmp > max_len ){

                max_len=tmp;

                qw=io;

            }

            t[i]=io;

            io+=strlen(io)+;

        }

        int flag=;

        for(int j=;j<=n;j++){

            if( find(qw,t[j]) !=  ){

                flag=;

                break ;

            }

        }

        if(flag){

            printf("%s\n",qw);

        }

        else{

            printf("No\n");

        }

    }

    return ;

}

another KMP

#include<iostream>

#include<cstdio>

#include<cmath>

#include<string>

#include<vector>

using namespace std;

typedef long long int LL;

int Sunday(string text, string pattern){

    int i = , j = , k;

    int m = pattern.size();

    if(pattern.size() <=  || text.size() <= )

        return -;

    for(; i<text.size();) {

        if(text[i] != pattern[j]) {

            for(k=pattern.size() - ; k>=; k--) {

                if(pattern[k] == text[m])

                    break;

            }

            i = m-k;

            j = ;

            m = i+pattern.size();

        }

        else {

            if(j == pattern.size()-)

                return i-j;

            i++;

            j++;

        }

    }

    return -;

}

vector<string> v;

int main()

{

    ios::sync_with_stdio(false);

    int T;

    cin>>T;

    while(T--)

    {

        int n;

        cin>>n;

        v.clear();

        string t,text;

        for(int i=;i<n;i++)

        {

            cin>>t;

            if(text.length()<t.length())

                text=t;

            v.push_back(t);

        }

        int f=;

        for(int i=;i<n;i++)

        {

            if(Sunday(text,v[i])== -)

            {

                f=;

                break;

            }

        }

        if(f)

            cout<<text<<endl;

        else

            cout<<"No"<<endl;

    }

    return ;

}

Sunday algorithm

巴特西

HDU 6208 The Dominator of Strings【AC自动机/kmp/Sunday算法】

最新文章

热门文章