检查字符串是否是Prolog中的子字符串

Question

有没有办法检查字符串是否是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( "测试", "tesZting").

它返回yes,但是应该返回no.

Answer 1

目前尚不清楚你的意思是字符串.但既然你说你把它转换成一个列表,你可能意味着原子.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卷.

Answer 2

Prolog 字符串是列表，其中列表的每个元素都是表示相关字符的代码点的整数值。该字符串与列表"abc"完全相同（假设您的 prolog 实现使用 Unicode 或 ASCII，否则值可能会有所不同）。[97,98,99]这导致了这个（从 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 子字符串，字符串中每个字符之间有一个，一个位于第一个字符之前，一个位于最后一个字符之后。