0

我想在 prolog 中创建 KMP 并开始像这样工作。不幸的是，我无法创建 Prolog 所需的前缀表？考虑到 prolog 是一种逻辑语言，我做得对吗？

compare(CharAtStartPos,CharAtNextPos,StartPos,NextPos,PrefixList,S,N,P):-
    CharAtStartPos=CharAtNextPos,write('Equal'),
    N is NextPos+1,
    string_chars(N,Element),
    write("Element is"), write(Element),
    S is StartPos+1,!;
    CharAtStartPos\=CharAtNextPos,NextPos\=0,write('Not equal'),
    value is NextPos-1,
    nth0(value,PrefixList, N),!;
    write('Else'),
    string_chars(0,Element),
    P = Element,write("Element is"),
    write(Element),
    S is StartPos+1.

loop(CharAtStartPos,CharAtNextPos,StartPos,NextPos,TextLength,PrefixList):-
    StartPos<TextLength,
    write('Start position is: '),write(StartPos),nl,
    compare(CharAtStartPos,CharAtNextPos, StartPos,NextPos,PrefixList,S,N,P),
    loop(CharAtStartPos,CharAtNextPos,S,N,TextLength,P),!;
    StartPos=TextLength,
    write("Loop end"),
    write(PrefixList).

createPrefixTable(Text,TextLength, PrefixList):-
    getTextAsList(Text,ListText),
    getTextLength(Text,TextLength),
    StartPos=1,NextPos=0,
    nth0(0,ListText,CharAtStartPos), nth0(1,ListText,CharAtNextPos),
    write(StartPos),write(NextPos),nl,
    write(CharAtStartPos),write(CharAtNextPos),nl,
    loop(CharAtStartPos,CharAtNextPos,StartPos, NextPos,TextLength, PrefixList),
    write(PrefixList),
    write("Finish").
4

1 回答 1

1

您使用 of;来实现析取不是惯用的，也不正确。即使;存在，您也应该几乎总是使用单独的子句。这将使问题更清楚：

loop(CharAtStartPos,CharAtNextPos,StartPos,NextPos,TextLength,PrefixList):-
    StartPos<TextLength,
    write('Start position is: '),write(StartPos),nl,
    compare(CharAtStartPos,CharAtNextPos, StartPos,NextPos,PrefixList,S,N,P),
    loop(CharAtStartPos,CharAtNextPos,S,N,TextLength,P).
loop(CharAtStartPos,CharAtNextPos,StartPos,NextPos,TextLength,PrefixList):-
    StartPos=TextLength,
    write("Loop end"),
    write(PrefixList).

第二条不PrefixList以任何方式绑定。调用者将永远无法从该谓词中获取信息！

我认为您可能想要添加一个“累加器”参数，该参数通过递归调用“构建”前缀列表。当递归停止时，最终结果应该是累加器的值。像这样的东西（未以任何方式测试）：

loop(CharAtStartPos, CharAtNextPos, StartPos, NextPos, TextLength, PrefixList0, PrefixList) :-
    StartPos < TextLength,
    write('Start position is: '), write(StartPos), nl,
    compare(CharAtStartPos, CharAtNextPos, StartPos, NextPos, PrefixList0, S, N, PrefixList1),
    loop(CharAtStartPos, CharAtNextPos, S, N, TextLength, PrefixList1, PrefixList).
loop(CharAtStartPos, CharAtNextPos, StartPos, NextPos, TextLength, PrefixList, PrefixList):-
    StartPos = TextLength,
    write("Loop end"),
    write(PrefixList).

来自“外部”的初始调用需要传递一个合适的初始累加器值，例如：

loop(CharAtStartPos, CharAtNextPos, StartPos, NextPos, TextLength, [], PrefixList)
于 2020-08-24T13:17:19.290 回答