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 has a suffix T such that, and
- X is a prefix of T
Here's the code:
substring(X,S) :-
append(_,T,S) ,
append(X,_,T) ,
X \= []
.
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.