[POJ 3080] Blue Jeans

发表于 | 分类于 ， ，
本文字数： 12k

链接

\(\text{POJ - 3080 Blue Jeans}\)

题意

  给你\(m\)个长度为60字符串，求它们的最长公共子串，如果有多个最长公共子串，输出字典序最小的，如果不存在或者最长公共子串的长度小于3则输出no significant commonalities；

  数据范围：共\(n\)组测试样例，每组一个\(m\)，\(2\leq m\leq 10\).

分析

  由于数据范围比较小，我们可以\(kmp+\)暴力，假如\(m\)个串的集合为\(s\)，那么我们枚举\(s[0]\)的所有长度\(\geq\) 3的所有子串，那么答案存在，必为其中的某一个，我们枚举这些子串，看对于一个子串是否能够同时和\(s[1\dots m]\)进行匹配成功，我们可以将得到的\(s\)集合排个序，使得我们找到一个可以与\(s[1\dots m]\)所有串匹配的子串，就可以直接输出它；

  这里我用的java，对于s集合中串的排序，c++里的我们可以写一个compare函数作为sort函数的第三个参数，对于java是有点类似的，见代码。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
import java.lang.Integer;

/**
 * Created by Messick on 2019/10/26.
 */

public class Main {
    public static int [] next = new int[105];
    public static int n, m;
    public static void main(String[] args) {
        Scanner input = new Scanner(new BufferedInputStream(System.in));
        PrintWriter out = new PrintWriter(System.out);
        int t = input.nextInt();
        while (t-- > 0) {
            int n = input.nextInt();
            n--;
            String s = input.next();
            Vector<String> v = new Vector<String>();
            int len = s.length();
            for (int i = 0; i < len; i++)
                for (int j = i + 3;j <= len; j++)
                    v.add(s.substring(i, j));
            Collections.sort(v, new Comparator<String>() {
                @Override
                public int compare(String o1, String o2) {
                    if (o1.length() == o2.length())return o1.compareTo(o2);
                    if (o1.length() < o2.length()) return 1;
                    else return -1;
                }
            });
//            for (int i = 0; i < v.size();i++)
//                System.out.println(v.get(i));
            String [] so = new String [15];
            for (int i = 0; i < n; i++)
                so[i] = input.next();
            int flag = -1;
            for (int i = 0; i < v.size(); i++) {
                flag = i;
                kmp(v.get(i));
                for (int j = 0; j < n; j++) {
                    if (match(so[j], v.get(i)))continue;
                    flag = -1;
                    break;
                }
                if (flag != -1)break;
            }
            if (flag == -1)System.out.println("no significant commonalities");
            else System.out.println(v.get(flag));
        }
    }
    public static void kmp(String s) {
        Arrays.fill(next, 0);
        int l = s.length();
        for (int i = 2, j = 0; i <= l; i++) {
            while (j > 0 && s.charAt(i - 1) != s.charAt(j)) j = next[j];
            if (s.charAt(i - 1) == s.charAt(j))j++;
            next[i] = j;
        }
    }
    public static boolean match(String s1, String s2) {
        int l1 = s1.length(), l2 = s2.length();
        for (int i = 1, j = 0; i <= l1; i++) {
            while (j > 0 && (j == l2 || s1.charAt(i - 1) != s2.charAt(j)))j = next[j];
            if (s1.charAt(i - 1) == s2.charAt(j))j++;
            if (j == l2)return true;
        }
        return false;
    }
}