比较多个子字符串

发布于 2024-09-25 14:48:06 字数 347 浏览 10 评论 0原文

我正在尝试编写一个基本的 DNA 测序仪。其中，给定两个相同长度的序列，它将输出相同的字符串，最小长度为3。所以输入

abcdef dfeabc

将返回

1 abc

我不知道如何去解决这个问题。我可以比较两个字符串，看看它们是否完全相等。从那里，我可以比较 length-1 字符串大小，即如果 dfeabc 包含 abcde。但是，我怎样才能让程序处理所有可能的字符串，最小大小为 3 个字符？一个问题是对于上面的 length-1 示例，我还必须执行字符串 bcdef 并进行比较。

原文

I'm attempting to write a basic dna sequencer. In that, given two sequences of the same length, it will output the strings which are the same, with a minimal length of 3.
So input of

abcdef dfeabc

will return

1 abc

I am not sure how to go about solving the problem.
I can compare the two strings, and see if they are completely equal. From there, i can compare length-1 string size, i.e. if dfeabc contains abcde. However, how can i get the program to do all possible strings, down to a minimal size of 3 characters?
One issue is for the above example of length-1, I'd also have to do the string bcdef and compare that.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

芸娘子的小脾气 2024-10-02 14:48:07

简单的方法是获取字符串 A 的每个子字符串，然后查看它是否在字符串 B 中。

以下是简单的方法：

for ( int i = 0; i < a.length; i++ ) {
   for ( int j = i+1; j <= a.length; j++ ) {
       if (b.contains(a.substring(i, j))) {
           //if longer than last found match, record this match
       }
   }
}

稍微更优化的方法是首先查看较长的子字符串，以便匹配的第一个子字符串必然是最长的。

for ( int length = a.length; length > 0; length-- ) {
     for ( int i = 0; i + length < a.length; i++ ) {
         if ( b.contains(a.substring(i, i+length)) ) {
             //this is the biggest match
         }
     }
}

The naive way would be to get every single substring of string A and see if it's in string B.

Here's the naive way of doing that:

for ( int i = 0; i < a.length; i++ ) {
   for ( int j = i+1; j <= a.length; j++ ) {
       if (b.contains(a.substring(i, j))) {
           //if longer than last found match, record this match
       }
   }
}

The slightly more optimal way would be to look at longer substrings first, so that the first substring that matches is necessarily the longest.

for ( int length = a.length; length > 0; length-- ) {
     for ( int i = 0; i + length < a.length; i++ ) {
         if ( b.contains(a.substring(i, i+length)) ) {
             //this is the biggest match
         }
     }
}

回复收藏 0 原文