暴力公共子串之“Blue Jeans”

题目大意：

　　输入 T 组数据，每组数据第一行是一个 m（2<=m<=10）。

　　给 m 个长度恰好是 60 的串，只由 'A','G','C','T' 构成。

　　找出并输出它们最长的且是最小字典序的公共子串，如果子串长度小于 3 ，则输出 no significant commonalities 。

　　样例：（所有的示例输入串其实都是一样长的，字体问题）

　　　　　　GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATA

　　　　　　AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA　　　　

　　　　　　GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATA

　　　　　　GATACTAGATACTAGATACTAGATACTAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA

　　　　　　GATACCAGATACCAGATACCAGATACCAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA

　　　　　　CATCATCATCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC

　　　　　　ACATCATCATAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

　　　　　　AACATCATCATTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT

　　　　　　————————————————————————————————————————————

　　　　　　no significant commonalities

　　　　　　AGATAC

　　　　　　CATCATCAT

解题思路：

　　利用 Java 语言中的 str.substring(int st,int ed) 和 str1.compareTo(str2) 以及 str1.indexOf(str2) 三个方法实现。

　　两种方法将在 AC代码下方进行讲解。

　　数据范围和串的长度都很小，只需要暴力枚举所有子字符串，一一比对即可。

AC代码：

 1 import java.util.*;
 2 
 3 public class Main{
 4 
 5     static String public_substring = "";
 6 
 7     static void check(String sub,String dna[]){
 8         int flag = 0;
 9         for(int i = 0;i < dna.length;i ++){
10             if(dna[i].indexOf(sub) == -1){flag = 1;break;}
11         }
12         if(flag == 0){
13             if(public_substring.length() == 0){public_substring = sub;}
14             if(sub.compareTo(public_substring) < 0 && public_substring.length() != 0){
15                 if(sub.length() >= public_substring.length()){public_substring = sub;}
16                 
17             }
18         }
19     }
20     
21     public static void main(String[] args){
22         Scanner sc = new Scanner(System.in);
23         int T = sc.nextInt();
24         while(T > 0){
25             int n = sc.nextInt();
26             String enter = sc.nextLine();        
27             String dna[] = new String[n];
28             for(int i = 0;i < n;i ++){
29                 dna[i] = sc.nextLine();
30             }
31             for(int i = 60;i >= 3;i --){
32                 for(int j = 0;j <= 60 - i;j ++){
33                     String t = dna[0].substring(j,j + i);
34                     check(t,dna);
35                     //System.out.println(t);
36                 }
37             }
38             if(public_substring.length() >= 3){
39                 System.out.println(public_substring);
40             }
41             else{
42                 System.out.println("no significant commonalities");
43             }
44             public_substring = "";
45 
46             T --;
47         }
48     }
49 }

一开始判断语句出现失误，导致子串不判断字典序，WA了一次，后来稍作修正就过了。

下面稍作讲解 str.substring(int st,int ed) 等三个方法。

　　substring()

　　　　作用是是取子串的操作，里面的整型变量数量如果是一个，就代表从某索引一直取到末尾。

　　　　如果有两个，代表从第一个索引取到第二个索引，但是第二个索引取不到。

　　compareTo()

　　　　作用是字符串的比较，如果前者字典序大于后者，返回正值，等于返回 0 ，小于返回负值。

　　indexOf()

　　　　作用为判断是否含有子串且返回出现第一次的索引，没有则返回 -1 。

　　　　括号内字符串为被判断的子串。

用一段示例程序进行以上三种方法的说明：

 1 import java.util.*;
 2 
 3 class Main{
 4     public static void main(String[] args){
 5 
 6         String STR  = "Just_do_it.";
 7         
 8         System.out.println(STR.substring(6));
 9         System.out.println(STR.substring(0,5));
10 
11         String cmp1 = "aabbcc";
12         String cmp2 = "zzbbcc";
13         String cmp3 = "aabbcc";
14 
15         System.out.println(cmp1.compareTo(cmp2));
16         System.out.println(cmp2.compareTo(cmp1));
17         System.out.println(cmp1.compareTo(cmp3));
18 
19         String str1 = "aabbccddee";
20         String str2 = "bbcc";
21         String str3 = "abc";
22     
23         System.out.println(str1.indexOf(str2));
24         System.out.println(str1.indexOf(str3));
25 
26     }
27 }
28 
29 //output
30 
31 //o_it.
32 //Just_
33 
34 //-25
35 //25
36 //0
37 
38 //2
39 //-1

从代码可以看出：

　　在 substring 里的索引是 6 的时候，取到了从索引 6 开始且包括 6 的后续所有字符。

　　在 substring 里的索引是 0 和 5 的时候，取到了从索引 0 开始且包括 0 的后续至索引是 5 但不包括 5 的所有字符。

　　可以说是一个左闭右开的区间。

　　compareTo 的返回值其实就是字典序相减的值，如 a - z == -25 和 z - a == 25 以及完全相同时的 0 。

　　indexOf 的返回主其实是返回了第一次子字符串出现的索引处，或者是完全不存在的 -1 。