hdu 2328 Corporate Identity

点击打开链接hdu 2328

思路：kmp+暴力枚举子串

分析：
1 题意要求最长的公共子串，由于每一串的长度最长不超过200，所以可以选择暴力枚举最短的单词的子串来求出ans
2 利用kmp来匹配

代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;

#define MAXN 4010
#define N 210

int n;
int next[MAXN];
char words[MAXN][N];

/*qsort*/
int cmp(const void *str1 , const void *str2){
   return strlen((char *)str1)-strlen((char *)str2);
}

/*求next*/
void getNext(char *str){
   int len = strlen(str);
   next[0] = next[1] = 0;

   for(int i = 1 ; i < len ; i++){
      int j = next[i];
      while(j && str[i] != str[j])
          j = next[j];
      next[i+1] = str[i] == str[j] ? j+1 : 0;
   }
}

/*匹配函数*/
bool find(char *text , char *str){
    int n = strlen(text);
    int m = strlen(str);

    int j = 0;
    for(int i = 0 ; i < n ; i++){
       while(j && text[i] != str[j])
           j = next[j];
       if(str[j] == text[i])
           j++;
       if(j == m)
           return true;
    }
    return false;
}

int main(){
   int max;
   char ans[MAXN];
   while(scanf("%d%*c" , &n) && n){
      for(int i = 0 ; i < n ; i++)
         scanf("%s" , words[i]);

      qsort(words , n , sizeof(words[0]) , cmp);

      int pos;
      char tmp[N];
      int len = strlen(words[0]);
      max = 0;

      for(int i = 0 ; i < len ; i++){
         memset(tmp , '\0' , sizeof(tmp));
         pos = 0;
         for(int j = i ; j < len ; j++){
            tmp[pos++] = words[0][j];
            getNext(tmp);

            int vis = 1;
            for(int k = 1 ; k < n ; k++){
               if(!find(words[k] , tmp)){
                  vis = 0;
                  break;
               }
            }
            if(vis && max < pos){
               max = pos;
               memcpy(ans , tmp , sizeof(tmp));
            }
            else if(vis && max == pos && strcmp(ans , tmp) > 0)
               memcpy(ans , tmp , sizeof(tmp));
         }
      }

      if(max)
        printf("%s\n" , ans);
      else
        printf("IDENTITY LOST\n");
   }
   return 0;
}