Java查找字符串中最长的重复序列
在此程序中，我们需要查找已在原始字符串中重复多次的子字符串。 >
在上面的字符串中，子字符串bdf是最长的序列，已重复两次。
该程序的算法如下。
算法
main()
步骤1: START
步骤2: 定义字符串str ="acbdfghybdf"
步骤3: SET String lrs =""
步骤4: 计算长度。
步骤5: SET i = 0。直到i < n。重复步骤6至步骤10
步骤6: SET j = i + 1。直到j < n。重复步骤7至步骤9
步骤7: 在字符串x中调用lcp()。
步骤8: if(x.length()> lrs.length())然后lrs = x
步骤9: j = j + 1
步骤10: i = i +1
步骤11: 打印步骤。
步骤12: END
lcp(String s，String t)
步骤1: START
步骤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: END
程序:
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
