CSharp  Java  Python  Swift  GO  WPF  Ruby  Scala  F#  JavaScript  SQL  PHP  Angular  HTML
Q. Program to find the longest repeating sequence in a string.ExplanationIn this program, we need to find the substring which has been repeated in the original string more than once.
In the above string, the substring bdf is the longest sequence which has been repeated twice. Algorithm
SolutionPython#Checks for the largest common prefix def lcp(s, t): n = min(len(s),len(t)); for i in range(0,n): if(s[i] != t[i]): return s[0:i]; else: return s[0:n]; str = "acbdfghybdf"; lrs=""; n = len(str); for i in range(0,n): for j in range(i+1,n): #Checks for the largest common factors in every substring x = lcp(str[i:n],str[j:n]); #If the current prefix is greater than previous one #then it takes the current one as longest repeating sequence if(len(x) > len(lrs)): lrs=x; print("Longest repeating sequence: "+lrs); Output: Longest repeating sequence: bdf C#include <stdio.h> #include <string.h> #define MIN(x, y) (((x) < (y)) ? (x) : (y)) //Userdefined substring function that will take string(str), position(p) and no of character(len) as input //Produces result c as output void substring(char s[], char sub[], int p, int len){ int c = 0; while (c < len) { sub[c] = s[p+c]; c++; } sub[c] = '\0'; } //Function thats gives the longest common prefix among two strings. int lcp(char s[], char t[],char a[]){ int n = MIN(strlen(s),strlen(t)); for(int i = 0; i < n; i++){ if(s[i] != t[i]){ substring(s,a,0,i); return 0; } } substring(s,a,0,n); return 0; } int main() { char str[] = "acbdfghybdf"; char lrs[30], x[30], res[30], sub[30],sub1[30]; int i,j,n = strlen(str); for(i = 0; i < n; i++){ for(j = i+1; j < n; j++){ //For comparing each substring with every other substring substring(str,sub,i,n); substring(str,sub1,j,n); cp(sub,sub1,x); //lrs keeps track of the longest repeating sequence if(strlen(x) > strlen(lrs)) strncpy(lrs, x, strlen(x)); } } printf("Longest repeating sequence: %s",lrs); return 0; } Output: Longest repeating sequence: bdf JAVApublic 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); } } Output: Longest repeating sequence: bdf C#using System; public class Program { //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[i] != t[i]){ return s.Substring(0,i); } } return s.Substring(0,n); } public static void Main() { String str = "acbdfghybdf"; String lrs=""; int n = str.Length; for(int i = 0; i < n; i++){ for(int j = i+1; j < ni; j++){ //Checks for the largest common factors in every substring String x = lcp(str.Substring(i),str.Substring(j)); //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; } } Console.WriteLine("Longest repeating sequence: "+lrs); } } Output: Longest repeating sequence: bdf PHP<!DOCTYPE html> <html> <body> <?php //Checks for the largest common prefix function lcp($s, $t){ $n = min(strlen($s),strlen($t)); for($i = 0; $i < $n; $i++){ if($s[$i] != $t[$i]){ return substr($s,0,$i); } } return substr($s,0,$n); } $str = "acbdfghybdf"; $lrs=""; $n = strlen($str); for($i = 0; $i < $n; $i++){ for($j = ($i+1); $j < ($n$i); $j++){ //Checks for the largest common factors in every substring $x = lcp(substr($str,$i),substr($str,$j)); //If the current prefix is greater than previous one //then it takes the current one as largest repeating sequence if(strlen($x) > strlen($lrs)) { $lrs=$x; } } } echo "Longest repeating sequence: $lrs"; ?> </body> </html> Output: Longest repeating sequence: bdf
Next TopicPrograms List
