序言找到類似的信件在2個字

Question

我有這樣的問題，我需要找到最長的單詞由來自2個字的信，這信必須在相同的順序像原話，例如xabred和pppaed必須返回aed。我不知道如何做到這一點在序言

Answer 1

如果我理解正確的要求，要求是將（經重列）謂詞找到最長子兩個給定的字符串（原子實際上）。如果長度相同，最長，則需要列出。這表示結果是一個或多個單詞的列表。

下面是它該做的作業的刺，但現在看來，這可能是一個有點「笨拙」，效率低下，特別是如果你考慮很長的字符串：

% Give a list of the longest matching words (substrings) 
matchwords(W1, W2, Results) :- 
    setof(R, matchw(W1, W2, R), RSet), % Collect all the matching substrings 
             % and their lengths 
    reverse(RSet, Set),    % Order by longest first 
    highest(Set, Results).    % keep only the highest ones 

% match atom-string W1 and W2 yielding atom-string Result of length N 
matchw(W1, W2, N-Result) :- 
    atom_chars(W1, A1), 
    atom_chars(W2, A2), 
    matchl(A1, A2, R), 
    length(R, N), 
    atom_chars(Result, R). 

% find a matching sublist between the first two lists 
matchl([H|T1], [H|T2], [H|T]) :- 
    matchl(T1, T2, T). 
matchl([H1|T1], [H2|T2], R) :- 
    H1 \= H2, 
    (matchl(T1, [H2|T2], R) ; matchl([H1|T1], T2, R)). 
matchl([], _, []). 
matchl([_|_], [], []). 

% Keep the highest elements at the front of a list of N-W pairs 
highest([_-W], [W]). 
highest([N1-W1,N2-_|_], [W1]) :- 
    N1 > N2. 
highest([N1-W1,N2-W2|T], [W1|WT]) :- 
    N1 = N2, 
    highest([N2-W2|T], WT). 

幾個例子：

| ?- matchwords(xabred, pppaed, Matches). 

Matches = [aed] ? a 

(2 ms) no 
| ?- matchwords(abcdef, acbedf, Matches). 

Matches = [acef,acdf,abef,abdf] ? a 

no 

這是歸結爲Longest Common Sequence Problem。上面的代碼並不試圖實施本文提供的必要解決方案。

Answer 2

sl(A, B, C) :- 
    atom_chars(A, Alist), 
    atom_chars(B, Blist), 
    intersection(Alist, Blist, Clist), 
    atom_chars(C, Clist). 

試運行：

?- sl(xabred, pppaed, X). 
X = aed. 

Answer 3

讓我們先找到任何字符公共子序列（我假設我們正在與人物的名單工作）：

common(Xs, Ys, [C|Cs]) :- 
    append(_,[C|Xs1],Xs), 
    append(_,[C|Ys1],Ys), 
    common(Xs1, Ys1, Cs). 
common(_, _, []). 

這將產生所有的解決方案在回溯：

?- common([a, b, c, d], [e, c, d, b], Cs). 
Cs = [b] 
Yes (0.00s cpu, solution 1, maybe more) 
Cs = [c, d] 
Yes (0.00s cpu, solution 2, maybe more) 
Cs = [c] 
Yes (0.00s cpu, solution 3, maybe more) 
Cs = [d] 
Yes (0.02s cpu, solution 4, maybe more) 
Cs = [] 
Yes (0.03s cpu, solution 5) 

你現在可以採用findall/3或setof/3來收集所有解決方案，並篩選出最長的解決方案。另外，下面顯示瞭如何修改代碼，這樣它首先返回最長的解決方案：

ordered_common(Xs, Ys, Cs) :- 
    le_min_length(Xs, Ys, Cs), 
    common(Xs, Ys, Cs). 

le_min_length([_|Xs], [_|Ys], [_|Zs]) :- 
    le_min_length(Xs, Ys, Zs). 
le_min_length(_, _, []). 

這樣一來，你可以減少搜索一旦交付你喜歡的解決方案。

?- ordered_common([a, b, c, d], [e, c, d, b], Cs). 
Cs = [c, d] 
Yes (0.00s cpu, solution 1, maybe more)