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

川长思鸟来 2023-10-06 19:23 4阅读 0赞

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

#### 问题： ####

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 1]

#### 思路： ####

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

子序列的组成即字符串的其中一些字符被选中，另外的字符不被选中，被选中的字符对应二进制数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函数

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 3]

#### 代码： ####

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());
            }
        }
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/6127a42fda674b7087d533bcd24e5d2e.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/b3188659efd5411d93b722e7b8dd02e0.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/fb469610ca19434ea72f80ed886d8466.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 3]: https://img-blog.csdnimg.cn/195fb01992df4aa9b4c8811d20157a20.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16