兩個大字符串中的部分字符串匹配

我正在尋找一種高效的算法來查找2個大字符串中的所有部分匹配。例如，兩個大字符串中的部分字符串匹配

string 1: "Thisismyfirststring" 
string 2: "searchismyfirtestring"

這應返回「他」，「hisismyfir」，「串」等

這可能嗎？

問候..

來源

2015-08-23 G Narayan

花點時間，格式化您的問題並使其可讀。目前我無法得到你想要的東西。另外請確保您附上您認爲有效/無效的相關代碼。 – SMA

構建一個布爾矩陣M，其中M（I，J）告訴你，如果一個字符串的第i個字符其他的第j個字符匹配。一個匹配的子字符串現在是M中的對角線true，所以現在走矩陣並尋找那些。

來源

2015-08-23 06:14:55 Joni

謝謝喬尼。你能詳細說一下嗎？否則，我們是否有任何有效的內置包，因爲我正在查看至少3000個字符的字符串，並且匹配可能會發生約300-400個字符。 –

我所描述的基本上是[最長公共子串]（https://en.wikipedia.org/wiki/Longest_common_substring_problem）的動態編程算法，您可以輕鬆地適應您的目的。 3000×3000字符的字符串導致只有10MB的布爾矩陣，所以這不是一個大問題。如果這是用於蛋白質或DNA測序，是的，有效的包裝。 – Joni

兩個大字符串中的部分字符串匹配

回答

相關問題