假設我們有兩個字串“abcdefgh”和“abudesh”。我希望解決方案是一個串列 ["ab", "de", "h"]。所以，我想要一個最大連接的子字串串列，它們對于兩個字串都是相同的。這有名字嗎？解決它的好方法是什么？
編輯：我需要說順序并不重要，例如，如果我們有兩個字串“abcdefg”和“defkabc”，結果是[“abc”，“def”]。
uj5u.com熱心網友回復：
使用：
- Biopython的pairwise2對齊兩個序列；
- itertools.groupby對“最大連接的子串”進行分組。
from Bio import pairwise2
from itertools import groupby
def maxConnectedSubstrings(strA, strB):
alignment = pairwise2.align.globalxx(strA, strB)[0]
grouped = groupby(zip(alignment.seqA, alignment.seqB), key=lambda p: p[0] == p[1])
return [''.join(ca for ca,cb in g) for k,g in grouped if k]
print( maxConnectedSubstrings('abcdefgh', 'abudesh') )
# ['ab', 'de', 'h']
解釋
首先，我們對齊序列。結果alignment = pairwise2.align.globalxx(strA, strB)[0]是：
alignment.seqA = 'abcdefgh'
alignment.seqB = 'abude-sh'
對齊演算法找到了添加'-'序列以對齊它們的最佳方法。
然后，我們使用groupbyon zip(alignment.seqA, alignment.seqB)。的zip(...)是對一個序列（從seqA字符，從seqB字符）。我們用 key 將這些對分組lambda p: p[0] == p[1]，得到以下結果：
grouped = groupby(zip(alignment.seqA, alignment.seqB), key=lambda p: p[0] == p[1])
grouped = [
(True, [('a', 'a'),
('b', 'b')]),
(False, [('c', 'u')]),
(True, [('d', 'd'),
('e', 'e')]),
(False, [('f', '-'),
('g', 's')]),
(True, [('h', 'h')])
]
最后，我們丟棄 False 組，并加入每個 True 組的字母。
uj5u.com熱心網友回復：
我可以提供用 C 創建的問題的解決方案。
#include <iostream>
#include <vector>
#include <string>
using namespace std;
void showContentVectorString(vector<string>& input)
{
for(int i=0; i<input.size(); i)
{
cout<<input[i]<<", ";
}
return;
}
void findEqualParts(string string0, string string1)
{
string temporary;
vector<string> strings;
for(int i=0; i<string0.size(); i)
{
for(int j=0; j<string1.size(); j)
{
if(string0[i]==string1[j])
{
temporary.push_back(string0[i]);
i;
if(j==string1.size()-1)
{
strings.push_back(temporary);
temporary.clear();
--i;
}
}
else
{
if(temporary.empty()==false)
{
strings.push_back(temporary);
}
temporary.clear();
}
}
}
cout<<"strings <- ";
showContentVectorString(strings);
return;
}
void solve()
{
findEqualParts("abcdefgh", "abudesh");
cout<<endl;
findEqualParts("abcdefg", "defkabc");
cout<<endl;
return;
}
int main()
{
solve();
return 0;
}
結果如下：
strings <- ab, de, h,
strings <- abc, def,
如果您需要對解決方案的解釋，請寫下相應的注釋。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/401798.html
標籤：算法