检查字符串是否是Prolog中的子字符串 [英] Check if string is substring in Prolog

问题描述

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

Is there a way to check if a string is a substring of another string in Prolog? I tried converting the string to a list of chars and subsequently checking if the first set is a subset of the second that that doesn't seem to be restrictive enough. This is my current code:

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").

isSubstring("test","tesZting").

它返回yes，但应该返回no.

it returns yes, but should return no.

推荐答案

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

Prolog strings are lists, where each element of the list is the integer value representing the codepoint of the character in question. The string "abc" is exactly equivalent to the list [97,98,99] (assuming your prolog implementation is using Unicode or ASCII, otherwise the values might differ). That leads to this (probably suboptimal from a Big-O perspective) solution, which basically says that X is a substring of S if

• S 有一个后缀 T，这样，并且
• X 是 T 的前缀

代码如下:

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

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

We restrict X to being something other than the empty list (aka the nil string ""), since one could conceptually find an awful lot of zero-length substrings in any string: a string of length n has 2+(n-1) nil substrings, one between each character in the string, one preceding the first character and one following the last character.

这篇关于检查字符串是否是Prolog中的子字符串的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！