白板的微信
2021-06-07 13:55:39
我有兩個(gè)字符串,第一個(gè)是主字符串,第二個(gè)是從字符串。它們都包含相似的值,除了奴隸將添加或刪除字符。我需要找到字符從偏移主的字符串從為每個(gè)字符串主字符串。我目前正在使用百分比作為在從屬字符串中查找類似偏移量的算法。例如;const master = 'The chicken is blue, but not really a chicken';const slave = 'This large bird is blue, but is really a dog';function slaveOffset(m, offset, s): number { return Math.floor(s.length * (offset / m.length));}console.log(slaveOffset(master, 15, slave)); // prints 12當(dāng)從主站翻譯位置 15(讀作“雞是”)時(shí),從站位置計(jì)算為 12。讀作“這個(gè)大 b”,因?yàn)槭褂冒俜直雀静粶?zhǔn)確(不考慮添加或刪除字符)。正確的值應(yīng)該是 18(讀作“大鳥是”),因?yàn)橹髌屏恳浴笆恰苯Y(jié)束。我需要一個(gè)算法slaveOffset()來處理添加和刪除的字符并找到最可能的從偏移量。它不需要過于準(zhǔn)確,但應(yīng)該解決由于字符變化引起的大偏差問題。
1 回答

SMILET
TA貢獻(xiàn)1796條經(jīng)驗(yàn) 獲得超4個(gè)贊
這是計(jì)算機(jī)科學(xué)中的一個(gè)經(jīng)典問題,通常稱為“數(shù)據(jù)比較”或簡(jiǎn)稱為“差異”。最常見的算法應(yīng)用最長(zhǎng)公共子序列技術(shù),但在一般情況下,這是一個(gè) NP-hard 問題,因此應(yīng)用各種啟發(fā)式方法來獲得“足夠好”的結(jié)果,通常由循環(huán)中的人進(jìn)行調(diào)整。
查找一些diff
算法以獲得一些想法。
在您的情況下,您可能希望從“從屬字符串從哪里開始與主字符串不同以及從哪里再次變得相同”的啟發(fā)式開始。字符串匹配前兩個(gè)字符,但下一次獲得超過 3 個(gè)字符的匹配序列時(shí),將出現(xiàn)在字符,i
和 處s
。這些點(diǎn)成為您可以在slaveOffset
函數(shù)中使用的標(biāo)記。
添加回答
舉報(bào)
0/150
提交
取消