HDU 2328 Corporate Identity（发现新大陆之KMP专题不用KMP也能过系列）

悠悠 2022-06-09 00:29 80阅读 0赞

Beside other services, ACM helps companies to clearly state their “corporate identity”, which includes company logo but also other signs, like trademarks. One of such companies is Internet Building Masters (IBM), which has recently asked ACM for a help with their new identity. IBM do not want to change their existing logos and trademarks completely, because their customers are used to the old ones. Therefore, ACM will only change existing trademarks instead of creating new ones.  
  
After several other proposals, it was decided to take all existing trademarks and find the longest common sequence of letters that is contained in all of them. This sequence will be graphically emphasized to form a new logo. Then, the old trademarks may still be used while showing the new identity.  
  
Your task is to find such a sequence.

Input

The input contains several tasks. Each task begins with a line containing a positive integer N, the number of trademarks (2 ≤ N ≤ 4000). The number is followed by N lines, each containing one trademark. Trademarks will be composed only from lowercase letters, the length of each trademark will be at least 1 and at most 200 characters.  
  
After the last trademark, the next task begins. The last task is followed by a line containing zero.

Output

For each task, output a single line containing the longest string contained as a substring in all trademarks. If there are several strings of the same length, print the one that is lexicographically smallest. If there is no such non-empty string, output the words “IDENTITY LOST” instead.

Sample Input

3
    aabbaabb
    abbababb
    bbbbbabb
    2
    xyz
    abc
    0

Sample Output

abb
    IDENTITY LOST

题解：

题意：

求一堆串的最长公共子串，同样长输出字典序最小的那个，没有输出一句话

思路：

枚举最短的那个串的所有子串，然后暴力查找。。

我看了很多博客都是用KMP做的，最近发现一个库函数strstr也可以实现KMP的功能，然后就抱着尝试的态度用了下没有用kmp。。。然后ac了！！！

用的时间好像比一般的KMP还快一些，只用了300ms，不过kmp还是要练的一会补上kmp的做法，这里放上strstr的做法

科普：

strstr函数一般情况下是比KMP要快一些的，除非有线性情况比如aaaaaaaaaaaaaaaaaaaaaaa，最坏复杂度是o（n的平方）

KMP函数因为预处理要花一些时间，但是最坏复杂度是o（n），所以如果想偷懒可以尝试些strstr能不能过hhhhh省了好多代码

代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<vector>
    #include<deque>
    using namespace std;
    #define lson k*2
    #define rson k*2+1
    #define M (t[k].l+t[k].r)/2
    #define INF 1008611111
    #define ll long long
    #define eps 1e-15
    struct node//存二维字符串组，因为不知道怎么直接用char型的二维字符串按照长度排序就直接用结构体了
    {
        char s[205];
    }a[4005];
    int cmp(node x,node y)//根据长度排序
    {
        return strlen(x.s)<strlen(y.s);
    }
    int main()
    {
        int i,j,k,len,tag,flag,t,maxx;
        char p[205];//存当前匹配串
        char temp[205];//存答案串
        int n;
        while(scanf("%d",&n)!=EOF&&n)
        {
            for(i=0;i<n;i++)
            {
                scanf("%s",&a[i].s);
            }
            flag=0;
            sort(a,a+n,cmp);//排序后取最短的枚举子串
            len=strlen(a[0].s);
            maxx=0;
            for(i=0;i<len;i++)//遍历所有子串
            {
                t=len;
                while(t>i&&t-i+1>maxx)//做了下优化，当前串长小于当前最大公共串直接退出
                {
                    if(t==len)//第一次就全部赋满值，后面的那几次直接在最后一个加上‘\0’就行了，加上这个快了一倍
                    {   for(j=i,k=0;j<t;j++,k++)
                        {
                            p[k]=a[0].s[j];
                        }
                        p[k]='\0';
                    }
                    else
                    {
                        p[t-i]='\0';
                    }
                    tag=1;
                    for(j=1;j<n;j++)
                    {
                        if(strstr(a[j].s,p)==NULL)//这个函数相当于扩展KMP的功能，还省去了一大段代码
                        {
                            tag=0;
                            break;
                        }
                    }
                    if(tag)
                    {
                        if(strlen(p)>maxx||strlen(p)==maxx&&strcmp(temp,p)>0)//按是否更长，等长比较字典序
                        {
                            maxx=strlen(p);
                            strcpy(temp,p);
                            flag=1;
                        }
                        break;
                    }
                    t--;
                }
            }
            if(!flag)
                printf("IDENTITY LOST\n");
            else
            {
                printf("%s\n",temp);
            }
        }
        return 0;
    }

然后下面是扩展KMP的写法。。用时700ms左右，就是上面的修改成了KMP写法，就不打注释了

代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<vector>
    #include<deque>
    using namespace std;
    #define lson k*2
    #define rson k*2+1
    #define M (t[k].l+t[k].r)/2
    #define INF 1008611111
    #define ll long long
    #define eps 1e-15
    struct node
    {
        char s[205];
    }a[4005];
    int Next[205];
    int slen, tlen;
    void init(char T[])
    {
        int i,j;
        i=0,j=-1;
        Next[0]=-1;
        while(T[i])
        {
            if(j==-1||T[i]==T[j])
            {
                i++;
                j++;
                Next[i]=j;
            }
            else
                j=Next[j];
        }
    }
    int KMP_Index(char T[],char S[])
    {
        int i=0,j=0;
        init(T);
        while(i<slen&&j<tlen)
        {
            if(j==-1||S[i]==T[j])
            {
                i++;j++;
            }
            else
                j=Next[j];
        }
        if(j==tlen)
            return i-tlen;
        else
            return -1;
    }
    int cmp(node x,node y)
    {
        return strlen(x.s)<strlen(y.s);
    }
    int main()
    {
        int i,j,k,len,tag,flag,t,maxx;
        char p[205];
        char temp[205];
        int n;
        while(scanf("%d",&n)!=EOF&&n)
        {
            for(i=0;i<n;i++)
            {
                scanf("%s",&a[i].s);
            }
            flag=0;
            sort(a,a+n,cmp);
            len=strlen(a[0].s);
            maxx=0;
            for(i=0;i<len;i++)
            {
                t=len;
                while(t>i&&t-i+1>maxx)
                {
                    if(t==len)
                    {   for(j=i,k=0;j<t;j++,k++)
                        {
                            p[k]=a[0].s[j];
                        }
                        p[k]='\0';
                    }
                    else
                    {
                        p[t-i]='\0';
                    }
                    tlen=strlen(p);
                    tag=1;
                    for(j=1;j<n;j++)
                    {
                        slen=strlen(a[j].s);
                        if(KMP_Index(p,a[j].s)==-1)
                        {
                            tag=0;
                            break;
                        }
                    }
                    if(tag)
                    {
                        if(strlen(p)>maxx||strlen(p)==maxx&&strcmp(temp,p)>0)
                        {
                            maxx=strlen(p);
                            strcpy(temp,p);
                            flag=1;
                        }
                        break;
                    }
                    t--;
                }
            }
            if(!flag)
                printf("IDENTITY LOST\n");
            else
            {
                printf("%s\n",temp);
            }
        }
        return 0;
    }