Prolog在2个单词中找到相似的字母

Question

我有这样的问题，我需要找到最长的单词由 2 个单词的字母组成，并且这些字母必须与原始单词中的顺序相同，例如 xabred 和 pppaed 必须返回 aed。我不知道如何在 Prolog 中执行此操作

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 .上面的代码并不试图实现本文中提供的命令式解决方案。