解题思路

这道题要求找出所有给定商标中共同包含的最长子串，如果有多个相同长度的子串，则选择字典序最小的那个。解题的关键在于高效地遍历和验证所有可能的子串：

1. 枚举子串：以第一个商标为基准，生成其所有可能的子串
2. KMP算法：使用KMP字符串匹配算法验证每个子串是否存在于其他所有商标中
3. 结果筛选：维护当前最长且字典序最小的公共子串

题意分析

本题要求从多个商标中找出共同的最长子串，具体要求：

• 输入处理：读取多个由小写字母组成的字符串（商标）
• 公共子串：找到所有商标共有的最长子串
• 输出要求：若存在，输出最长且字典序最小的子串；否则输出"IDENTITY LOST"

关键点：

• 子串必须是连续的
• 所有商标必须包含该子串
• 需考虑长度和字典序的双重条件

标程实现

以下是完整的标程实现，使用KMP算法进行高效子串匹配：

#include<cstring>
#include<cstdio>
using namespace std;
typedef long long ll;
char s[4005][205],p[205];  // 存储商标和当前子串
int n[205];                // KMP算法的next数组

// KMP算法预处理：计算next数组
void get(char p[]){
    int j=-1,i=0;
    n[0]=-1;
    int len1=strlen(p);
    while(i<len1){
        if(j==-1 || p[i]==p[j]){
            i++,j++;
            if(p[i]!=p[j]) n[i]=j;
            else n[i]=n[j];
        }
        else j=n[j];
    }
}

// KMP算法：在s中查找p是否存在
int kmp(char s[],char p[]){
    int i=0,j=0;
    int len1=strlen(s),len2=strlen(p);
    while(i<len1 && j<len2){
        if(j==-1 || s[i]==p[j]){
            i++,j++;
        }
        else j=n[j];
    }
    if(j==len2) return 1;  // 匹配成功
    return 0;              // 匹配失败
}

int main(){
    int m;
    while(~scanf("%d",&m) && m){  // 读取测试用例，直到输入0
        char ans[205]="";         // 存储最终结果
        
        // 读取所有商标
        for(int i=0;i<m;i++)
            scanf("%s",s[i]);
        
        int len=strlen(s[0]);     // 以第一个商标为基准
        
        // 枚举第一个商标的所有子串
        for(int i=0;i<len;i++){
            for(int j=i;j<len;j++){
                int cnt=0;
                // 生成子串
                for(int k=i;k<=j;k++)
                    p[cnt++]=s[0][k];
                p[cnt]='\0';
                
                // KMP预处理
                get(p);
                
                // 检查该子串是否存在于所有商标中
                int flag=1;
                for(int k=0;k<m;k++){
                    if(!kmp(s[k],p)) {flag=0;break;}
                }
                
                // 更新最长公共子串
                if(flag){
                    if(strlen(p)==strlen(ans) && strcmp(p,ans)<0){
                        strcpy(ans,p);  // 长度相同但字典序更小
                    }
                    else if(strlen(p)>strlen(ans))
                        strcpy(ans,p);  // 更长的子串
                }
            }
        }
        
        // 输出结果
        if(strcmp(ans,"")==0) puts("IDENTITY LOST");
        else printf("%s\n",ans);
    }
    return 0;
}

代码解释

1. KMP算法：

   • get函数：预处理模式串p，计算next数组用于失配回退
   • kmp函数：在主串s中查找模式串p，返回是否存在

2. 枚举子串：

   • 以第一个商标为基准，生成所有可能的子串
   • 外层循环控制子串起始位置，内层循环控制结束位置

3. 结果筛选：

   • 维护当前最长且字典序最小的公共子串
   • 每次找到更长的子串或字典序更小的等长子串时更新结果

4. 输入处理：

   • 处理多组测试用例，直到输入0为止
   • 确保正确读取每个商标字符串

该实现通过枚举子串和KMP算法高效验证，确保在合理时间内找到最长公共子串，满足题目要求。