54
Java Program to find the longest repeating sequence in a string
In this program, we need to find the substring which has been repeated in the original string more than once.
A | b | D | F | A | A | b | d | f | h |
In the above string, the substring bdf is the longest sequence which has been repeated twice.
The algorithm of the program is given below.
Algorithm
main()
- STEP 1: START
- STEP 2: DEFINE string str = “acbdfghybdf”
- STEP 3: SET String lrs = ” “
- STEP 4: CALCULATE length.
- STEP 5: SET i =0. REPEAT STEP 6 to STEP 10 UNTIL i<n.
- STEP 6: SET j =i+1. REPEAT STEP 7 to STEP 9 UNTIL j<n.
- STEP 7: CALL lcp() in String x.
- STEP 8: if(x.length()>lrs.length()) then lrs =x
- STEP 9: j =j + 1
- STEP 10: i =i +1
- STEP 11: PRINT lrs.
- STEP 12: END
lcp(String s, String t)
- STEP 1: START
- STEP 2: SET n = Math.min(s.length(), t.length())
- STEP 3: SET i =0. REPEAT STEP 4 to STEP 5 UNTIL i<n
- STEP 4: if(s.charAt(i) != t.charAt(i)) then RETURN s.substring(0, i)
- STEP 5: i= i+1
- STEP 6: RETURN s.substring(0,n)
- STEP 7: END
Program:
Output:
Longest repeating sequence: bdf
Next TopicJava Programs