hdu1238 参考答案

   1 /*
   2 zju1374 hdu1238 暴力搜索
   3 ymc 2008/6/19
   4 题目大意：
   5 给定n个字符串，求长度最长的一个串s，
   6 使得s或者s的逆串是所有串的子串。
   7 注意：子串与子序列的区别。
   8 解题思路：
   9 找n个字符串中最短的字符串，然后暴力搜索
  10 */
  11 #include <iostream>
  12 #include <string>
  13 using namespace std;
  14 const int N=101;
  15 char s[N][N];
  16 int n;
  17 int id,len;//保存n个字符串中，最短字符串的索引号与长度
  18 
  19 //最短串从start开始，长度为len的子串，第k个字符串中，是否能与这个子串匹配
  20 bool Match1(int start,int len,int begin,int k)
  21 {
  22     int i=0;
  23     while(i<len)//顺序匹配
  24     {
  25         if(s[id][start+i]!=s[k][begin+i])
  26             break;
  27         i++;
  28     }
  29     if(i>=len)
  30         return true;
  31     i=0;
  32     int end=begin+len-1;
  33     while(i<len) //逆序匹配
  34     {
  35         if(s[id][start+i]!=s[k][end-i])
  36             break;
  37         i++;
  38     }
  39     if(i>=len)
  40         return true;
  41     return false;
  42 }
  43 
  44 //其它所有串中，是否能与最短串从start开始，长度为len的子串匹配
  45 bool Match(int start,int len)
  46 {
  47     int tmp;
  48     bool find;
  49     for(int k=0;k<n;k++)
  50     {
  51         find=false;
  52         tmp=strlen(s[k]);
  53         for(int i=0;i<=tmp-k;i++)
  54         {
  55             if(Match1(start,len,i,k))
  56             {
  57                 find=true;
  58                 break;
  59             }
  60         }
  61         if(find==false)
  62             return false;
  63     }
  64     return true;
  65 }
  66 int Solve()
  67 {
  68     id=0;len=100;
  69     for(int i=0;i<n;i++)//找最短串
  70         if(strlen(s[i])<len)
  71         {
  72             len=strlen(s[i]);
  73             id=i;
  74         }
  75     for(int k=len;k>=1;k--)//是否有长度为k的公共串
  76         for(int i=0;i<=len-k;i++)
  77             if(Match(i,k))
  78                 return k;
  79     return 0;
  80 }
  81 int main()
  82 {
  83     int test;
  84     scanf("%d",&test);
  85     while(test-->0)
  86     {
  87         scanf("%d",&n);
  88         for(int i=0;i<n;i++)
  89         {
  90             scanf("%s",s[i]);
  91         }
  92         int ans=Solve();
  93         printf("%d\n",ans);
  94     }
  95 }