Соответствие строк без использования встроенных функций

Question

Я хочу найти запрос (строку) в теме (другая строка).

Запрос может отображаться целиком или по частям, но не будет переупорядочен. Например, если запрос равен 'da', и предмет 'dura', он по-прежнему соответствует.

Мне не разрешено использовать строковые функции, такие как strfind или find.

Answer 1

Если это домашнее задание, я предлагаю вам ознакомиться с объяснением, которое предшествует коду, а затем попробуйте самостоятельно, прежде чем смотреть на фактический код.

ниже код ищет все вхождения символов в query строки в пределах subject строки (переменные m и связанные ii, jj). Затем он проверяет все возможные порядки этих случаев (переменная test). Заказ является «приемлемым», если он содержит все необходимые символы (cond1) в увеличении позиций (cond2). Результат (переменная result) является положительным, если существует хотя бы один приемлемый порядок.

subject = 'this is a test string'; 
query = 'ten'; 

m = bsxfun(@eq, subject.', query); 
%'// m: test if each char of query equals each char of subject 
[ii jj] = find(m); 
jj = jj.'; %'// ii: which char of query is found within subject... 
ii = ii.'; %'// jj: ... and at which position 
test = nchoosek(1:numel(jj),numel(query)).'; %'// test all possible orders 
cond1 = all(jj(test) == repmat((1:numel(query)).',1,size(test,2))); 
%'// cond1: for each order, are all chars of query found in subject? 
cond2 = all(diff(ii(test))>0); 
%// cond2: for each order, are the found chars in increasing positions? 
result = any(cond1 & cond2); %// final result: 1 or 0 

Код может быть улучшена за счет использования лучшего подхода в отношении к test, то есть не испытывая все возможные приказы по nchoosek.

Answer 2

Matlab позволяет просматривать исходные тексты встроенных функций, поэтому вы всегда можете попробовать прочитать код, чтобы посмотреть, как это сделали разработчики Matlab (хотя, вероятно, это будет очень сложно). (спасибо Луис за исправление)

Поиск строки в другой строке - это проблема базовой информатики. Вы можете прочитать об этом в любом количестве ресурсов, например Wikipedia.

Ваше требование неперестраивающихся частичных совпадений напоминает проблему биоинформатики для сопоставления вариантов сращивания с геномной последовательностью.

Вы можете решить вашу проблему, используя алгоритм выравнивания последовательности, такой как Smith-Waterman, модифицированный для работы со всеми английскими символами, а не только с базами данных.

Действительно ли это вопрос из биоинформатики? Если это так, вы должны пометить его как таковой.

Answer 3

Ограничения делают это довольно простым с помощью одного цикла. Представьте, что у вас есть два индекса, первоначально указывающих на первый символ обеих строк, теперь сравните их - если они не совпадают, увеличьте индекс предмета и повторите попытку. Если они это сделают, увеличьте оба. Если вы достигли конца запроса в этот момент, вы его нашли. Фактическая реализация должна быть достаточно простой, и я не хочу делать все работа для вас;)