John Stone

1996-04-04

中国 河北

找出一个字符串中重复出现的首个最长字符串的算法

芦苇小白

Dec 29, 2020 12:50:35 PM 81

简单说明

标题有点绕, 简单地说这个算法就是找出一个字符串中重复出现的字符串(非字符). 且这个字符串是最长的, 若存在两个相同长度的重复字符串, 则取第一个出现的字符串的值.

举个例子

比如祖国你好, 你好祖国这个字符串中, 祖国你好都出现了两次, 且这两个串长度相等. 那么这个方法会返回第一个出现的也就是祖国.

再比如在北京市北京市朝阳区东大桥路东大桥路环球金融中心B座, 环球金融中心B座12层这个字符串中, 北京市出现了三次, 东大桥路出现了两次, 环球金融中心B座出现了两次, 并且环球金融中心B座是重复出现的字符串中长度最长的, 那么算法会返回环球金融中心B座.

之所以会写这么一个变态的方法, 是因为在一个信用卡反欺诈的项目中, 有一个字符串修正的逻辑需要用到这个方法, 并且在网上并没有找到这方面的资料, 全都是找出重复字符的, 而非字符串. 故此自己写了一个方法, 发出来以便帮助遇到同样需求的朋友.

代码

/**
 * 测试类1
 * @author gsk
 */
public class Test1 {

    public static void main(String[] args){
        String testStr = new StringBuffer("北京市").append("北京市")
                .append("北京市东大桥路").append("北京市东大桥路")
                .append("北京市朝阳区东大桥路").append("北京市朝阳区东大桥路")
                .append("北京市朝阳区东大桥路环球金融中心B座").append("北京市朝阳区东大桥路环球金融中心B座").toString();

        String repeatStr = findMaxRepeatText(testStr);
        System.out.println(repeatStr);
    }


    /**
     * 找出一个字符串中重复出现的首个最长串
     * @param text
     * @return
     */
    public static String findMaxRepeatText(String text){
        char[] chars = text.toCharArray();
        StringBuffer buffer = new StringBuffer();
        int maxCount = 0;
        int frequency = 0;
        String tempStr = "";
        for(int i = 0; i < chars.length; i ++){
            if (!text.substring(i + 1).contains(buffer.toString() + chars[i])){
                if (maxCount < buffer.length()){
                    maxCount = buffer.length();
                    tempStr = buffer.toString();
                }
                buffer.setLength(0);
                i = (frequency ++);
                continue;
            }
            buffer.append(chars[i]);
        }
        return tempStr;
    }
}
输出结果

北京市朝阳区东大桥路环球金融中心B座

补充一下, 发布完这篇文章才发现下方推荐的类似文章里有我想要的…是我的搜索方式不对?

这是一个Java算法, 原理类似本篇
https://blog.csdn.net/hanruikai/article/details/81505862
这是一个C++的算法, 另一种原理, 通过正序查找和反序查找实现
https://blog.csdn.net/u011261670/article/details/80586558

拖动滑块验证
验证通过 验证失败

全部评论