lcs([ H|L1],[ H|L2],[H|Lcs]) :-
!,
lcs(L1,L2,Lcs).
lcs([H1|L1],[H2|L2],Lcs):-
lcs( L1 ,[H2|L2],Lcs1),
lcs([H1|L1], L2 ,Lcs2),
longest(Lcs1,Lcs2,Lcs),
!.
lcs(_,_,[]).
longest(L1,L2,Longest) :-
length(L1,Length1),
length(L2,Length2),
( Length1 > Length2
-> Longest = L1
; Longest = L2
).
到目前为止，这是我的代码。我如何对其进行优化，以便打印出前缀，例如:
["interview", "interrupt", "integrate", "intermediate"]
应该返回
"inte"对Prolog有点使用rust ，已经有一段时间没做过了:)
最佳答案
首先，让我们从相关的内容开始，但要简单得多。
:- set_prolog_flag(double_quotes, chars). % "abc" = [a,b,c]
prefix_of(Prefix, List) :-
append(Prefix, _, List).
commonprefix(Prefix, Lists) :-
maplist(prefix_of(Prefix), Lists).
?- commonprefix(Prefix, ["interview", "integrate", "intermediate"]).
Prefix = []
; Prefix = "i"
; Prefix = "in"
; Prefix = "int"
; Prefix = "inte"
; false.
(请参阅this答案，如何打印带有双引号的字符列表。)
这是Prolog中相当容易的部分。唯一的缺点是它没有给我们最大的值(value)，而是所有可能的解决方案，包括最大的值(value)。请注意，不需要知道所有字符串，例如:
?- commonprefix(Prefix, ["interview", "integrate", Xs]).
Prefix = []
; Prefix = "i", Xs = [i|_A]
; Prefix = "in", Xs = [i, n|_A]
; Prefix = "int", Xs = [i, n, t|_A]
; Prefix = "inte", Xs = [i, n, t, e|_A]
; false.
因此，作为响应，我们得到了对最后一个未知单词的部分描述。现在想象一下，稍后我们意识到
Xs = "induce"。 Prolog没问题:?- commonprefix(Prefix, ["interview", "integrate", Xs]), Xs = "induce".
Prefix = [], Xs = "induce"
; Prefix = "i", Xs = "induce"
; Prefix = "in", Xs = "induce"
; false.
实际上，无论是事后看来还是在实际查询之前都没有关系:
?- Xs = "induce", commonprefix(Prefix, ["interview", "integrate", Xs]).
Xs = "induce", Prefix = []
; Xs = "induce", Prefix = "i"
; Xs = "induce", Prefix = "in"
; false.
我们现在可以根据此公式来制定最大值吗？请注意，这实际上需要某种形式的额外量化器，对此我们在Prolog中没有任何直接规定。因此，我们必须将我们限制在某些我们知道会安全的情况下。最简单的方法是坚持单词列表不包含任何变量。我将为此使用
iwhen/2 。maxprefix(Prefix, Lists) :-
iwhen(ground(Lists), maxprefix_g(Prefix, Lists)).
maxprefix_g(Prefix, Lists_g) :-
setof(N-IPrefix, ( commonprefix(IPrefix, Lists_g), length(IPrefix, N ) ), Ns),
append(_,[N-Prefix], Ns). % the longest one
这种方法的缺点是，如果不知道单词列表，则会遇到实例化错误。
请注意，我们做出了一些假设(我希望确实如此)。特别是，我们假设正好有一个最大值。在这种情况下，这种情况成立，但总的来说，
Prefix可能有几个独立的值。此外，我们假设IPrefix将始终为地面。我们可以检查一下，只是为了确定。或者:maxprefix_g(Prefix, Lists_g) :-
setof(N, IPrefix^ ( commonprefix(IPrefix, Lists_g), length(IPrefix, N ) ), Ns),
append(_,[N], Ns),
length(Prefix, N),
commonprefix(Prefix, Lists_g).
在这里，前缀不必是一个前缀(在我们的情况下就是这样)。
但是，最好的是纯净版本，根本不需要求助于实例化错误。
关于list - 字符串列表的最长公共(public)前缀(LCP)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/47462530/