POJ3450最长公共子串【kmp】

题目大意：给定n个长度不超过200的字符串,n < 4000。求这些字符串的最长公共子串，若没有，则输出 “IDENTITY LOST”。

思路：

1.枚举第一个字符串的各个子串s，将s分别与其他字符串进行kmp，来找到可以取得的s的最大长度（这样就是一次枚举中所有字符串的公共子串），然后接着枚举子串s，更新这个长度，注意在长度相等时选取字典序小即可。

2.strcmp(a, b)比较a, b字符串，返回值为0则字符串相同。返回值大于0则a的字典序大于b的字典序，返回值小于0则a的字典序小于b的字典序。

3.strcpy(a, b)将b字符串复制给a,strncpy(a, b, len)将b字符串前len个长度的字符复制给a，注意需要手动给a添加结束符 '\0'.

代码：

 #include<stdio.h>

 #include<string.h>

 #include<algorithm>

 const int inf = 0x3f3f3f3f;

 using namespace std;

 char str[][], s[], res[], tt[];

 int next[], temp, s_len, str_len, flag;

 void get_next()

 {

     s_len = strlen(s);//模式串

     next[] = -;

     int j = , k = -;

     while(j < s_len)

     {

         if(k == - || s[j] == s[k])

         {

             j ++, k ++;

             next[j] = k;

         }

         else

             k = next[k];

     }

 }

 void kmp(int id)

 {

     temp = ;

     str_len = strlen(str[id]);

     int i = , j = ; //i文本串 j模式串

     int vis = ;

     while(i < str_len && j < s_len)

     {

         if(s[j] == str[id][i] || j == -)

         {

             vis = ;

             i ++, j ++;

         }

         else

             j = next[j];

         temp = max(temp, j);

     }

     if(!vis)

         flag = ;

 }

 int main()

 {

     int n, minn, ans_len, xx;

     while(scanf("%d", &n) != EOF)

     {

         if(n == )

             break;

         getchar();

         ans_len = -;

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

             scanf("%s", str[i]);

         int len = strlen(str[]);

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

         {

             minn = inf, xx = ;

             strcpy(s, str[] + i);

             get_next();

             flag = ;

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

             {

                 kmp(j);

                 if(flag == )

                 {

                     xx = ;

                     break;

                 }

                 minn = min(minn, temp);

             }

             if(xx == )

                 continue;

             if(minn > ans_len)

             {

                 ans_len = minn;

                 strncpy(res, s, ans_len);

                 res[ans_len] = '\0';

             }

             if(minn == ans_len)

             {

                 strncpy(tt, s, minn);

                 tt[minn] = '\0';

                 if(strcmp(res, tt) > )

                     strcpy(res, tt);

             }

         }

         if(ans_len ==  || ans_len == -)

             printf("IDENTITY LOST\n");

         else

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

     }

     return ;

 }

巴特西

POJ3450最长公共子串【kmp】

最新文章

热门文章