Проверьте, является ли строка подстрокой в ​​Прологе

Есть ли способ проверить, является ли строка подстрокой другой строки в Прологе? Я попытался преобразовать строку в список символов и впоследствии проверить, является ли первый набор подмножеством второго, что не кажется достаточно ограничительным. Это мой текущий код:

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

он возвращает да, но должен вернуть нет.

Источник

4 ответа

Решение

Строки пролога являются списками, где каждый элемент списка является целочисленным значением, представляющим кодовую точку рассматриваемого символа. Строка "abc" в точности соответствует списку [97,98,99] (при условии, что ваша реализация пролога использует Unicode или ASCII, в противном случае значения могут отличаться). Это приводит к этому (вероятно, неоптимальному с точки зрения Big-O) решению, которое в основном говорит, что X является подстрокой S, если

  • S имеет суффикс T такой, что и
  • X является префиксом T

Вот код:

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

Мы ограничиваем X тем, что он является чем-то иным, чем пустой список ""), поскольку концептуально можно найти огромное количество подстрок нулевой длины в любой строке: строка длиной n имеет 2+ (n-1) nil подстрок, одну между каждым символом в строке, одну перед первым символом и одну после последнего символа.

Источник

Непонятно, что вы подразумеваете под строкой. Но так как вы говорите, что конвертируете его в список, вы можете иметь в виду атомы. ИСО Пролог предлагает 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).
Источник

Используя DCG, вы можете сделать следующее: (SWI)

%                   anything  substring anything
substr(String) --> ([_|_];[]), String,  ([_|_];[]).

% is X a substring of Y ?
substring(X,Y) :- phrase(substr(X),Y).
Источник

Проблема с вашим isSubset/2,
Есть две разные ситуации, которые вы пытались отразить в одном предикате. Либо вы ищете первую позицию, которая будет пытаться соответствовать вашей подстроке, либо вы уже нашли эту точку и проверяете, совпадают ли строки.

isSubset([], _).
isSubSet(Substring, String) :-
    findStart(Substring, String, RestString),
    line_up(Substring, RestString).

findStart([], String, String).
findStart([H|T], [H|T1], [H|T1]).
findStart(Substring, [_|T], RestString) :-
    findStart(Substring, T, RestString).

line_up([], _).
line_up([H|T], [H|T1]) :-
    line_up(T, T1).

Вы можете объединить их в один предикат следующим образом:

isSublist([], L, L).
isSublist([H|T], [H|T1], [H|T1]) :-
    isSublist(T, T1, T1).
isSublist(L, [_|T], Rest) :-
    isSublist(L, T, Rest).
Источник
Другие вопросы по тегам