生命形式问题

一 问题描述

你可能想知道为什么大多数外星生命形式与人类相似，不同的是表面特征，如身高，颜色，皱纹，耳朵，眉毛等。少数人没有人类的相似之处:这些通常具有几何形状或无定形形状，如立方体，浮油或灰尘云。

答案在星际迷航一一下一代的第 146 集中给出，名为 The Chase。事实证明，绝大多数象限的生命形式最终都是一个普通 DNA 的大片段。

鉴于表示为字母串的几种生命形式的 DNA 序列，您将找到由超过一半的字符串共享的最长子字符串。

二 输入和输出

1 输入

标准输入包含几个测试用例。每个测试用例始于 1<=N<=100，生命形式的数目。接下来 n 行，每行包含一串小写字母，代表生命形式的 DNA 序列。每个 DNA 序列含有至少一个且不超过 1000 个字母。在最后一个测试用例之后包含0的行。

2 输出

对于每个测试用例，输出超过一半生命形式共享的最长字符串。如果有很多，则按字母顺序输出所有这些。如果没有至少一个字母的解决方案，则输出"?"。在测试用例之间留一空行。

三 输入和输出样例

1 输入样例

3

abcdefg

bcdefgh

cdefghi

3

xxx

yyy

zzz

0

2 输出样例

bcdefg

cdefgh

?

四 分析和设计

1 分析

本问题包括多个字符串，首先用一个原字符串中没有的字符将每个字符串连接起来，求解重复 N/2 次的最长子串。可采用后缀数组及二分法求解。

2 设计

a 将 N 个字符串连接起来，中间用特殊字符间隔。

b 求解 sa 数组。

c 求解 rank 数组和 height 数组。

d 使用二分法求解，对特定的长度 mid，判断是否满足 height[j] >=mid 的字符串个数是否大于等于 N/2，求出最大 mid 后，输出长度大于等于 mid 的所有的子串。

3 示例

abcdefg#bcdefgh#cdefghi

后缀排序后的前几个序列如下：

五 代码

package com.platform.modules.alg.alglib.poj3294;
 
public class Poj3294 {
    // 100 个字符串中间添加了 100 个，每个字符串最大 1000
    private int maxn = 100500;
    int belong[] = new int[maxn];
    int r[] = new int[maxn];
    int sa[] = new int[maxn];
    String s = "";
    // 名称数组
    int rank[] = new int[maxn];
    // 高度数组
    int height[] = new int[maxn];
    int n, k;
    int wa[] = new int[maxn];
    int wb[] = new int[maxn];
    int wv[] = new int[maxn];
    // c[]用于基数排序统计
    int c[] = new int[maxn];
 
    boolean cmp(int r[], int a, int b, int l) {
        return (r[a] == r[b]) && (r[a + l] == r[b + l]);
    }
 
    // 交换两个数组的内容 https://blog.csdn.net/m0_56793367/article/details/115599564
    public static void swap(int[] array1, int[] array2) {
        int tmp = 0;
        for (int i = 0; i < array1.length; i++) {
            tmp = array1[i];
            array1[i] = array2[i];
            array2[i] = tmp;
        }
    }
 
    void da(int r[], int sa[], int n, int m) {
        int i, k, p;
        int x[] = wa;
        int y[] = wb;
        for (i = 0; i < m; i++) // 基数排序
            c[i] = 0;
        for (i = 0; i < n; i++)
            c[x[i] = r[i]]++;
        for (i = 1; i < m; i++)
            c[i] += c[i - 1];
        for (i = n - 1; i >= 0; i--)
            sa[--c[x[i]]] = i;
        for (k = 1; k <= n; k <<= 1) {
            // 直接利用 sa 排序第二关键字
            p = 0;
            for (i = n - k; i < n; i++)
                y[p++] = i; // 补零的位置下标排在最前面
            for (i = 0; i < n; i++)
                if (sa[i] >= k)
                    y[p++] = sa[i] - k;
            // 基数排序第一关键字
            for (i = 0; i < n; i++)
                wv[i] = x[y[i]]; // 将第二关键字排序结果转换为名次，进行排序
            for (i = 0; i < m; i++)
                c[i] = 0;
            for (i = 0; i < n; i++)
                c[wv[i]]++;
            for (i = 1; i < m; i++)
                c[i] += c[i - 1];
            for (i = n - 1; i >= 0; i--)
                sa[--c[wv[i]]] = y[i];
            // 根据 sa 和 x 数组，重新计算新的x数组
            swap(x, y); // y 数组已经没有用，更新x需要使用x本身数据，因此放入y使用
            p = 1;
            x[sa[0]] = 0;
            for (i = 1; i < n; i++)
                x[sa[i]] = cmp(y, sa[i - 1], sa[i], k) ? p - 1 : p++;
            if (p >= n)//排序结束
                break;
            m = p;
        }
    }
 
    void calheight(int r[], int sa[], int n) {
        int i, j, k = 0;
        for (i = 1; i <= n; i++)
            rank[sa[i]] = i;
        for (i = 0; i < n; i++) {
            if (k > 0)
                k--;
            j = sa[rank[i] - 1];
            while (r[i + k] == r[j + k])
                k++;
            height[rank[i]] = k;
        }
    }
 
    boolean check(int mid, int n, int m, boolean flag) {
        int i = 2;
        boolean vis[];
        while (true) {
            vis = new boolean[105]; // 清零
            while (i <= n && height[i] < mid)
                i++;
            if (i > n)
                break;
            vis[belong[sa[i - 1]]] = true;//标记该字符串
            while (i <= n && height[i] >= mid) {
                vis[belong[sa[i]]] = true;//如果是自己的子串，只标记一次
                i++;
            }
            int cnt = 0;
            for (int j = 1; j <= m; j++)
                if (vis[j])
                    cnt++;
            if (cnt > m / 2) {
                if (!flag)
                    return true; // 立即返回1，否则输出，继续运行输出所有满足条件的子串
                else {
                    for (int j = sa[i - 1], t = 0; t < mid; j++, t++)
                        output += s.charAt(j);
                    output += "\n";
                }
            }
        }
        return false;
    }
 
    void solve(int L, int R) {
        int res = -1, mid;
        while (L <= R) {
            mid = (L + R) >> 1;
            if (check(mid, n, k, false)) {
                res = mid;
                L = mid + 1;
            } else
                R = mid - 1;
        }
        if (res == -1)
            output += "?\n";
        else
            check(res, n, k, true);//输出
    }
 
    public String output = "";
 
    public String cal(String input) {
        int len = 0;
        String[] line = input.split("\n");
        int count = 0;
        while (true) {
            s = "";
            k = Integer.parseInt(line[count++]);
            if (k == 0) {
                return output;
            }
 
            n = 0;
            for (int i = 1; i <= k; i++) { // 将 k 个字符串连接起来，中间用特殊字符间隔
                String str = line[count];
                count++;
                this.s += str;
                if (i == 1)
                    len = this.s.length();
                for (int j = 0; j < str.length(); j++) {
                    belong[n] = i; // 标记属于第 i 个字符串
                    r[n] = str.charAt(j) - 'a' + 1;//a-z 97-122
                    n++;
                }
                this.s += "#"; // 35
                r[n] = 100 + i;
                n++;
            }
            n--;
            r[n] = 0; // 末尾补一个比所有值都小的数
            da(r, sa, n + 1, 300);
            calheight(r, sa, n);
            solve(1, len);
            output += "\n";
        }
    }
}

 六 测试