暴力枚举+位运算：最长公共子序列Ⅱ

问题：

思路：

子序列不一定是连续序列，为了求最长公共子序列，需要枚举出每个字符串的所有子序列。

子序列的组成即字符串的其中一些字符被选中，另外的字符不被选中，被选中的字符对应二进制数1，未被选中的字符对应二进制0。因此子序列的选取和二进制数联系起来了，对于n位的字符串，子序列总数为2 ^ n – 1，对应二进制数000…001 ~ 111…111。

使用for循环枚举所有子序列的情况，循环变量p的取值从1直到(1 << n) – 1，即对应二进制数000…001 ~ 111…111，我们需要遍历所有字符，查看该字符是否被选中，即对应位在二进制数中是否为1，设000…001表示字符串s的第一个字符s[0]被选中，100…000表示s[n-1]被选中，对应字符的下标index即为二进制数中1左移的位数。因此使用for循环，循环变量表示下标index，标识字符的二进制数即为1 << index，我们只要用标识字符的二进制数与p进行与运算即可，所得到的数不为0即表示当前字符被选中，把该字符追加到结果字符串

对于环的处理，我们需要将字符串的长度扩充一倍，即s += s，然后枚举起始位置即可，枚举完原字符串的最后一个字符后结束。

对于候选公共子序列的存储和更新，我们可以设置一个map存储之前认为正确的公共子序列，名为legal。设置一个map存储当前处理字符串对应的公共子序列，名为now。若当前遍历的子序列在legal中，则将该子序列put进now，每次遍历完后。将legal更新为now

对于最长公共子序列的选择，遍历最终的legal找出最长字符串即可

由于结果可能有多个，需输出字典序最小的，我们直接使用treeSet保存结果，自动进行字符串排序，头元素即为字典序最小的

需注意的点：

将legal更新为now不能使用=，需进行深拷贝，使用map的putAll函数

代码：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n, i, j, len, p, k;
        String str, temp, s;
        TreeSet<String> ans = new TreeSet<>();
        Map<String, Integer> legal = new HashMap<>();
        Map<String, Integer> now = new HashMap<>();
        while (scanner.hasNextInt()) {
            legal.clear();
            ans.clear();
            n = scanner.nextInt();
            scanner.nextLine();
            for (i = 0;i < n;i++) {
                now.clear();
                str = scanner.nextLine();
                len = str.length();
                str += str;
                for (j = 0;j < len;j++) {
                    // 处理环
                    s = str.substring(j, j + len);
                    // 枚举所有子序列的情况
                    for (p = 1;p < 1 << len;p++) {
                        temp = "";
                        // 遍历所有字符
                        for (k = 0;k < len;k++) {
                            if ((p & (1 << k)) != 0) {
                                temp += s.substring(k, k + 1);
                            }
                        }
                        if (i == 0 || legal.get(temp) != null) {
                            now.put(temp, 1);
                        }
                    }
                }
                legal.clear();
                legal.putAll(now);
            }
            len = 0;
            if (legal.size() != 0) {
                for (String ss : legal.keySet()) {
                    if (ss.length() > len) {
                        len = ss.length();
                        ans.clear();
                        ans.add(ss);
                    } else if (ss.length() == len) {
                        ans.add(ss);
                    }
                }
            }
            if (ans.size() == 0) {
                System.out.println(0);
                continue;
            }
            System.out.println(ans.first());
        }
    }
}