标题清洗引发的算法（两个字符串的最长公共子串）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了标题清洗引发的算法（两个字符串的最长公共子串），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2698字，纯文字阅读大概需要4分钟。

内容图文

前言

在做声音标题清洗的时候，需要将专辑的标题和声音的标题对比，如果他们的最长公共字符串长度大于三，则清除声音中的最长公共字符串，否则不清除。

解析

1. 把声音标题的字符串，放入x轴，把专辑标题的字符串，放入y轴。如下图一
   
   
   图一
   

2. 当x为1的时候，为 "平"，那么对应的 y轴上的字符，如果相同的话设置为1。
   如下图二

图二

1. 当y为1的时候，为 "平"， 那么对应的 x轴上的字符，如果相同的话设置为1。
   

2. 当x为2的时候，为 "凡"， 那么对应 y轴上的字符，如果相同的话，查看 x-1,y-1 对应的数字大小加1，标注后如下图三
   
   
   图三
   

3. 当x为3的时候， 为 "的"，那么对应y轴上的字符,如果相同的话，查看 x-1,y-1 对应的数字大小加1，标注后如下图四
   
   
   图四
   
   。。。。。

依次往下走，直到x上没有字符串为止。
这是一个比较经典的动态规划算法，能够了解他的状态转移方程为 dp[i][j]=dp[i][j] + 1 时间复杂度为 O(nm);

具体代码如下

  /**
     * @Author ouyangkang
     * @Description 清除两个字符串的最长公共子串，如果长度小于3 不清除
     * @Date 10:45 2019-10-31
     * @param albumTitle
     * @param trackTitle
     * @return java.lang.String
     **/
    private static String cleanTrackTitleFromAlbumTitle(String albumTitle, String trackTitle){

        if (StringUtils.isBlank(albumTitle) || StringUtils.isBlank(trackTitle)){
            return trackTitle;
        }
        Map<String, Integer> map = getLongestCommonSubstring(albumTitle, trackTitle);
        Integer len = map.get("len");
        Integer start = map.get("start");
        if (len > 3){
            start += 1;
            return trackTitle.replace(trackTitle.substring(start - len,start), "");
        }else {
            return trackTitle;
        }
    }

 /**
     * @Author ouyangkang
     * @Description 获取两个字符串最长公共子串
     * @Date 16:01 2019-10-31
     * @param albumTitle
     * @param trackTitle
     * @return java.util.Map<java.lang.String,java.lang.Integer>
    **/
    private static Map<String, Integer> getLongestCommonSubstring(String albumTitle, String trackTitle){
        Map<String, Integer> map = new HashMap<>();
        // 最长公共子串大小
        int len = 0;
        // 子串坐标
        int start = 0;
        // 最长公共子串大小 为 dp[i][j] = dp[i-1][j-1] + 1;
        int[][] dp = new int[albumTitle.length()][trackTitle.length()];
        for (int i = 0; i < albumTitle.length(); i++){
            for (int j = 0; j< trackTitle.length();j++){
                if (i==0 && albumTitle.charAt(0)== trackTitle.charAt(j)){
                    dp[0][j] = 1;
                    continue;
                }

                if (j==0 && albumTitle.charAt(i) == trackTitle.charAt(0)){
                    dp[i][0] = 1;
                    continue;
                }

                if(albumTitle.charAt(i) == trackTitle.charAt(j)){
                    dp[i][j] = dp[i-1][j-1] + 1;
                    if (dp[i][j] > len){
                        len = dp[i][j];
                        start = j;
                    }
                }
            }
        }
        // 记录长度
        map.put("len",len);
        // 记录声音标题的坐标
        map.put("start",start);
        return map;
    }

调用 cleanTrackTitleFromAlbumTitle方法，入参为 "平凡的世界", "平凡的时间01"。返回的字符串为 01

总结

能够在日常开发中，写一写算法，并应用到程序中，不是curd，也是比较有意思的一件事，清洗的过程是很复杂的，这只是其中一步清洗，其他的清洗涉及到一些正则表达式。一开始写了些能够实现功能的正则，但是在同事的提醒下，发现了很涉及到正则的回溯。emmmm.. 这就是另说了，下次博客补上。

内容总结

以上是互联网集市为您收集整理的标题清洗引发的算法（两个字符串的最长公共子串）全部内容，希望文章能够帮你解决标题清洗引发的算法（两个字符串的最长公共子串）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---