Check if string is substring in Prolog

MaVe picture MaVe · Nov 27, 2013 · Viewed 7.7k times · Source

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

If I test this with

isSubstring("test","tesZting").

it returns yes, but should return no.

Answer

false picture false · Nov 27, 2013

It is not clear what you mean by a string. But since you say you are converting it to a list, you could mean atoms. ISO Prolog offers atom_concat/3 and sub_atom/5 for this purpose.

| ?- 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.

Otherwise, use DCGs! Here's how

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

Acknowledgements

The first appearance of above definition of ... is on p. 205, Note 1 of

David B. Searls, Investigating the Linguistics of DNA with Definite Clause Grammars. NACLP 1989, Volume 1.