7

有没有办法检查一个字符串是否是 Prolog 中另一个字符串的子字符串？我尝试将字符串转换为字符列表，然后检查第一组是否是第二组的子集，这似乎不够严格。这是我当前的代码：

isSubstring(X,Y):-
        stringToLower(X,XLower),
        stringToLower(Y,YLower),
        isSubset(XLower,YLower).

isSubset([],_).
isSubset([H|T],Y):-
        member(H,Y),
        select(H,Y,Z),
        isSubset(T,Z).

stringToLower([],[]).
stringToLower([Char1|Rest1],[Char2|Rest2]):-
        char_type(Char2,to_lower(Char1)),
        stringToLower(Rest1,Rest2).

如果我用

isSubstring("test","tesZting")。

它返回是，但应该返回否。

4

4 回答 4

6

目前尚不清楚您所说的字符串是什么意思。但是，既然您说要将其转换为列表，则可能是指原子。ISO Prolog 提供atom_concat/3并sub_atom/5为此目的。

| ?- atom_concat(X,Y,'abc').
  X = '', Y = abc
; X = a, Y = bc
; X = ab, Y = c
; X = abc, Y = ''.

| ?- sub_atom('abcbcbe',Before,Length,After,'bcb').
  Before = 1, Length = 3, After = 3
; Before = 3, Length = 3, After = 1.

否则，请使用 DCG！就是这样

seq([]) --> [].
seq([E|Es]) --> [E], seq(Es).

... --> [] | [_], ... .

subseq([]) --> [].
subseq(Es) --> [_], subseq(Es).
subseq([E|Es]) --> [E], subseq(Es).

seq_substring(S, Sub) :-
   phrase((...,seq(Sub),...),S).

seq_subseq(S, Sub) :-
   phrase(subseq(Sub),S).

致谢

上述定义的第一次出现...是在 p 上。205，注 1

David B. Searls，用定从句语法研究 DNA 的语言学。NACLP 1989，第 1 卷。

于 2013-11-27T19:43:22.567 回答
1

Prolog 字符串是列表，其中列表的每个元素都是表示相关字符代码点的整数值。该字符串"abc"与列表完全相同[97,98,99]（假设您的 prolog 实现使用 Unicode 或 ASCII，否则值可能会有所不同）。这导致了这个（从 Big-O 的角度来看可能是次优的）解决方案，它基本上说 X 是 S 的子串，如果

  • S 有一个后缀 T 使得，并且
  • X 是 T 的前缀

这是代码：

substring(X,S) :-
  append(_,T,S) ,
  append(X,_,T) ,
  X \= []
  .

我们将 X 限制为不是空列表（也称为 nil 字符串""），因为从概念上讲，可以在任何字符串中找到大量零长度子字符串：长度为n的字符串有 2+( n -1) 个 nil 子字符串, 在字符串中的每个字符之间，一个在第一个字符之前，一个在最后一个字符之后。

于 2013-11-27T22:39:57.417 回答
1

问题出在你的isSubset/2.
您试图在一个谓词中捕获两种不同的情况。您正在寻找第一个位置来尝试匹配您的子字符串，或者您已经找到该点并正在检查字符串是否“对齐”。

isSubset([], _).
isSubSet(Substring, String) :-
    findStart(Substring, String, RestString),
    line_up(Substring, RestString).

findStart([], String, String).
findStart([H|T], [H|T1], [H|T1]).
findStart(Substring, [_|T], RestString) :-
    findStart(Substring, T, RestString).

line_up([], _).
line_up([H|T], [H|T1]) :-
    line_up(T, T1).

您可以将它们组合成一个谓词，如下所示：

isSublist([], L, L).
isSublist([H|T], [H|T1], [H|T1]) :-
    isSublist(T, T1, T1).
isSublist(L, [_|T], Rest) :-
    isSublist(L, T, Rest).
于 2013-11-28T07:52:55.300 回答
1

使用 DCG，您可以执行以下操作：（SWI）

%                   anything  substring anything
substr(String) --> ([_|_];[]), String,  ([_|_];[]).

% is X a substring of Y ?
substring(X,Y) :- phrase(substr(X),Y).
于 2014-06-22T16:19:26.763 回答