首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >比较多个子字符串

问比较多个子字符串
EN

Stack Overflow用户
提问于 2010-09-30 03:25:42
回答 3查看 1.3K关注 0票数 2

我在试着写一个基本的dna测序仪。因为,给定两个相同长度的序列,它将输出相同的字符串,最小长度为3。

代码语言:javascript
复制
abcdef dfeabc

将会返回

代码语言:javascript
复制
1 abc

我不知道该如何着手解决这个问题。我可以比较这两个字符串,看看它们是否完全相等。从那里,我可以比较长度为1的字符串大小,即如果dfeabc包含abcde。但是,如何才能让程序执行所有可能的字符串,最小长度不超过3个字符呢?一个问题是,对于上面的长度为1的例子,我还必须对字符串bcdef进行比较。

EN

回答 3

Stack Overflow用户

回答已采纳

发布于 2010-09-30 03:31:19

天真的方法是获取字符串A的每个子字符串,并查看它是否在字符串B中。

这是一种天真的方式:

代码语言:javascript
复制
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
       }
   }
}

稍微更理想的方法是先查看较长的子字符串,这样匹配的第一个子字符串就一定是最长的。

代码语言:javascript
复制
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
         }
     }
}
票数 1
EN

Stack Overflow用户

发布于 2010-09-30 03:32:57

如果您想以一种简单的方式解决这个问题,而不使用任何Java API进行搜索,您可以这样想:对于第一个字符串中的i和第二个字符串中的j这两个可能的起始索引,当第一个和第二个字符串中的相应字符相等时,在这两个索引中都前进一步,如果至少执行了3个步骤,则返回结果。

票数 0
EN

Stack Overflow用户

发布于 2010-09-30 03:55:23

您需要使用最长公共子串算法,这是一个动态编程问题。查看维基百科的entry获取算法的解释,查看here获取示例实现。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/3825096

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档