All substrings with same begin and end

Question

I have to solve a homework but I have a very limited knowledge of Prolog. The task is the following:
Write a Prolog program which can list all of those substrings of a string, whose length is at least two character and the first and last character is the same.

For example:

?- sameend("teletubbies", R).
R = "telet";
R = "ele";
R = "eletubbie";
R = "etubbie";
R = "bb";
false.

My approach of this problem is that I should iterate over the string with head/tail and find the index of the next letter which is the same as the current (it satisfies the minimum 2-length requirement) and cut the substring with sub_string predicate.

It was just an idea, but in code maybe it would look like this: sameend([H|T], R) :- sameend([T], R), % and there should be a recursive call again to check where the same character is and then sub_string() from H's postition to it's next occurence. — K. Nagy, Apr 15 '17 at 20:04

score 4 · Accepted Answer · edited May 23 '17 at 11:47

This depends a bit on what you exactly mean by a string. Traditionally in Prolog, a string is a list of characters. To ensure that you really get those, use the directive below. See this answer for more.

:- set_prolog_flag(double_quotes, chars).

sameend(Xs, Ys) :-
   phrase( ( ..., [C], seq(Zs), [C], ... ), Xs),
   phrase( ( [C], seq(Zs), [C] ), Ys).

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

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

score 1 · Answer 2 · answered Apr 16 '17 at 06:47

1

if your Prolog has append/2 and last/2 in library(lists), it's easy as

sameend(S,[F|T]) :-
    append([_,[F|T],_],S),last(T,F).

answered Apr 16 '17 at 06:47

CapelliC

59,646
5
47
90

All substrings with same begin and end

2 Answers2