0

所以我的问题与子字符串有关。

如何在起始字符串和三个结束字符串之一之间找到可能的最长子字符串？我还需要找到最大子字符串开始的原始字符串的索引。

所以：

开始字符串：“ATG”

3 个可能的结束字符串：“TAG”“TAA”“TGA”

一个示例原始字符串可能是：“SDAFKJDAFKATGDFSDFAKJDNKSJFNSDTGASDFKJSDNKFJSNDJFATGDSDFKJNSDFTAGSDFSDATGFF”所以结果应该给我： - 最长子字符串长度：23（来自子字符串 ATGDFSDFAKJDNKSJFNSDTGA） - 最长子字符串索引：10

我不能使用正则表达式。

谢谢你的帮助！

4

4 回答 4

0

嗯，这看起来很有趣。

似乎最直接的方法是构建自己的迷你有限状态机。您必须解析字符串中的每个字符并跟踪所有可能终止该序列的字符序列。

如果您击中“T”，则需要向前跳并查看下一个字符。如果它是“A”或“G”，则需要再次向前跳，否则，将这些标记添加到您的字符串中。继续该模式，直到到达原始字符串的末尾，或匹配您的终端模式之一。

所以，也许看起来像这样（简化示例）：

String longestSequence(String original) {
  StringBuilder sb = new StringBuilder();
  char[] tokens = original.toCharArray();
  for (int i = 0; i < tokens.length; ++i) {
    // read each token, and compare / look ahead to see if you should keep going or terminate.
  }
  return sb.toString();
}
于 2013-11-10T07:15:44.680 回答
0

将您的字符串与此正则表达式匹配：

ATG[A-Z]+(TAG|TAA|TGA)

如果发生多个匹配，则迭代并保留具有最高长度的匹配。

import java.util.regex.Matcher;
import java.util.regex.Pattern;

    // using pattern with flags
    Pattern pattern = Pattern.compile("ATG[A-Z]+(TAG|TAA|TGA)");

    Matcher matcher = pattern.matcher( yourInputStringHere );

    while (matcher.find()) {
        System.out.println("Found the text \"" + matcher.group()
                + "\" starting at " + matcher.start()
                + " and ending at index " + matcher.end());
    }
于 2013-11-10T08:09:49.627 回答
0

这可以说是最简单的方法，而且只有一行：

String target = str.replaceAll(".*ATG(.*)(TAG|TAA|TGA).*", "$1");

要查找索引：

int index = str.indexOf("ATG") + 3;

注意：我已将您的评论“我不能使用正则表达式”解释为“我不擅长正则表达式”，因为如果这是一个 java 问题，则可以使用正则表达式。

于 2013-11-10T08:14:03.013 回答
0

您的问题已经有一些漂亮而优雅的解决方案（波西米亚和好奇）。如果您仍然 - 如最初所述 - 不能使用正则表达式，这里有一个替代方案。这段代码不是特别优雅，正如所指出的，有更好的方法来做到这一点，但它至少应该清楚地向您展示解决问题背后的逻辑。

如何在起始字符串和三个结束字符串之一之间找到可能的最长子字符串？

首先，找到起始字符串的索引，然后找到每个结束字符串的索引，并获取每个结尾的子字符串，然后是它们的长度。请记住，如果未找到字符串，则其索引将为 -1。

    String originalString = "SDAFKJDAFKATGDFSDFAKJDNKSJFNSDTGASDFKJSDNKFJSNDJFATGDSDFKJNSDFTAGSDFSDATGFF";

    String STARTING_STRING = "ATG";

    String END1 = "TAG";
    String END2 = "TAA";
    String END3 = "TGA";

    //let's find the index of STARTING_STRING
    int posOfStartingString = originalString.indexOf(STARTING_STRING);

    //if found
    if (posOfStartingString != -1) {
        int tagPos[] = new int[3];

        //let's find the index of each ending strings in the original string
        tagPos[0] = originalString.indexOf(END1, posOfStartingString+3);
        tagPos[1] = originalString.indexOf(END2, posOfStartingString+3);
        tagPos[2] = originalString.indexOf(END3, posOfStartingString+3);

        int lengths[] = new int[3];

        //we can now use the following methods:
        //public String substring(int beginIndex, int endIndex)
        //where beginIndex is our posOfStartingString
        //and endIndex is position of each ending string (if found)
        //
        //and finally, String.length() to get the length of each substring

        if (tagPos[0] != -1) {
            lengths[0] = originalString.substring(posOfStartingString, tagPos[0]).length();
        }
        if (tagPos[1] != -1) {
            lengths[1] = originalString.substring(posOfStartingString, tagPos[1]).length();
        }
        if (tagPos[2] != -1) {
            lengths[2] = originalString.substring(posOfStartingString, tagPos[2]).length();
        }

    } else {
        //no starting string in original string
    }

lengths[] 表现在包含以 STARTING_STRING 开头的字符串长度和 3 个各自的结尾。然后只需找出哪个最长，您就会得到答案。

我还需要找到最大子字符串开始的原始字符串的索引。

这将是起始字符串开始的索引，在本例中为 10。

于 2013-11-10T21:52:42.803 回答