TheDeveloperBlog.com

Home | Contact Us

C-Sharp | Java | Python | Swift | GO | WPF | Ruby | Scala | F# | JavaScript | SQL | PHP | Angular | HTML

Program to Find the Longest Repeating Sequence in a String

Program to Find the Longest Repeating Sequence in a String on fibonacci, factorial, prime, armstrong, swap, reverse, search, sort, stack, queue, array, linkedlist, tree, graph etc.

<< Back to PROGRAM

Q. Program to find the longest repeating sequence in a string.

Explanation

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.

Algorithm

  1. Define a string and calculate its length.
  2. Define a function for the longest common prefix that is, it takes two strings as arguments and determines the longest group of characters common in between them.
  3. Using the same function, we will compare original string will all its substrings. Then, first for loop compare all the substrings with all the other substrings till we find the longest repeating sequence.
  4. Storing the longest string in the variable lrs if the length of x is greater than lrs.

Solution

Python

#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))
//User-defined 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

JAVA

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);
    }
}

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 < n-i; 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




Related Links:

.Net

.NET Array Dictionary List String 2D Async DataTable Dates DateTime Enum File For Foreach Format IEnumerable If IndexOf Lambda LINQ Parse Path Process Property Regex Replace Sort Split Static StringBuilder Substring Switch Tuple

Java

Core Array ArrayList HashMap String 2D Cast Character Console Deque Duplicates File For Format HashSet If IndexOf Lambda Math ParseInt Process Random Regex Replace Sort Split StringBuilder Substring Switch Vector While

Related Links

Adjectives Ado Ai Android Angular Antonyms Apache Articles Asp Autocad Automata Aws Azure Basic Binary Bitcoin Blockchain C Cassandra Change Coa Computer Control Cpp Create Creating C-Sharp Cyber Daa Data Dbms Deletion Devops Difference Discrete Es6 Ethical Examples Features Firebase Flutter Fs Git Go Hbase History Hive Hiveql How Html Idioms Insertion Installing Ios Java Joomla Js Kafka Kali Laravel Logical Machine Matlab Matrix Mongodb Mysql One Opencv Oracle Ordering Os Pandas Php Pig Pl Postgresql Powershell Prepositions Program Python React Ruby Scala Selecting Selenium Sentence Seo Sharepoint Software Spellings Spotting Spring Sql Sqlite Sqoop Svn Swift Synonyms Talend Testng Types Uml Unity Vbnet Verbal Webdriver What Wpf