Program to Find the Longest Repeating Sequence in a String

by Online Tutorials Library July 22, 2022

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.

In the above string, the substring bdf is the longest sequence which has been repeated twice.

Algorithm

Define a string and calculate its length.
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.
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.
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] = ‘

Program to Find the Longest Repeating Sequence in a String

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

Explanation

Algorithm

Solution

Python

C

Program to Convert Feet to cm

Program to print all abundant numbers between 1 to 100

You may also like