查找字符串中最长重复序列的Java程序

1 说明

在此程序中，我们需要找到已在原始字符串中重复多次的子字符串。

在上面的字符串中，子字符串bdf是最长的序列，已重复两次。

2 算法思路

main()函数

• 步骤1：开始
• 第2步：定义字符串str =“ acbdfghybdf”
• 步骤3： SET String lrs =“”
• 步骤4：计算长度。
• 步骤5： SET i = 0。直到i <n为止，将步骤6重复到步骤10。
• 步骤6：设定j = i + 1。重复步骤7至步骤9，直到j <n。
• 步骤7：在字串x中调用lcp（）。
• 步骤8： if（x.length（）> lrs.length（））然后lrs = x
• 步骤9： j = j + 1
• 步骤10： i = i +1
• 第11步：打印lrs。
• 步骤12：结束

lcp(String s, String t)函数

• 步骤1：开始
• 步骤2： SET n = Math.min（s.length（），t.length（））
• 步骤3： SET i = 0。直到i <n，将步骤4重复到步骤5
• 步骤4： if（s.charAt（i）！= t.charAt（i））然后返回s.substring（0，i）
• 步骤5： i = i + 1
• 步骤6：返回s.substring（0，n）
• 步骤7：结束

3 程序实现

/**
 * 一点教程网： http://www.yiidian.com
 */
public class LongestRepeatingSequence {  
    //Checks for the largest common prefix  
    public static String lcp(String s, String t){  
        int n = Math.min(s.length(),t.length());  
        for(int i = 0; i < n; i++){  
            if(s.charAt(i) != t.charAt(i)){  
                return s.substring(0,i);  
            }  
        }  
        return s.substring(0,n);  
    }  
  
    public static void main(String[] args) {  
        String str = "acbdfghybdf";  
        String lrs="";  
        int n = str.length();  
        for(int i = 0; i < n; i++){  
            for(int j = i+1; j < n; j++){  
                //Checks for the largest common factors in every substring  
                String x = lcp(str.substring(i,n),str.substring(j,n));  
                //If the current prefix is greater than previous one  
                //then it takes the current one as longest repeating sequence  
                if(x.length() > lrs.length()) lrs=x;  
            }  
        }  
        System.out.println("Longest repeating sequence: "+lrs);  
    }  
} 

以上代码输出结果为：

Longest repeating sequence: bdf