Quietly tell you

没有什么技术是一篇文档解决不了的,如果有,那就两篇。

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

简单说明

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

举个例子

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

 

再比如在北京市北京市朝阳区东大桥路东大桥路环球金融中心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

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注