问. 查找字符串中最长重复序列的程序。

2025年1月8日 | 阅读 4 分钟

说明

在此程序中，我们需要找到在原始字符串中重复出现一次以上的子字符串。

在上面的字符串中，子字符串 bdf 是重复出现两次的最长序列。

算法

定义一个字符串并计算其长度。
定义一个函数来查找最长公共前缀，即它接受两个字符串作为参数并确定它们之间最长的公共字符组。
使用相同的函数，我们将原始字符串与所有子字符串进行比较。然后，第一个 for 循环将所有子字符串与所有其他子字符串进行比较，直到找到最长的重复序列。
如果 x 的长度大于 lrs，则将最长的字符串存储在变量 lrs 中。

解决方案

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

输出

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

输出

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

输出

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

输出

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>

输出

Longest repeating sequence: bdf

下一个主题程序列表

问. 查找字符串中最长重复序列的程序。

说明

算法

解决方案

Python

C

JAVA

C#

PHP

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

程序

问. 查找字符串中最长重复序列的程序。

说明

算法

解决方案

Python

C

JAVA

C#

PHP

相关帖子

华氏度转摄氏度的程序

计算三角形面积的程序

确定一个字符串是否为另一个字符串的旋转的程序

打印数字图案 6 的程序

创建包含 n 个节点的单向链表并计算节点数量的程序

确定给定矩阵是否为单位矩阵的程序

编写查找二十面体（Icosahedron）面积的程序

查找字符串中重复单词的程序

计算矩形面积的程序

从循环链表末尾删除新节点的程序

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器