Найти шаблоны в строках

17

В этой задаче ваша задача - найти подстроки с заданной структурой.

вход

Ваш ввод должен состоять из двух непустых буквенно-цифровых строк, шаблона p и текста t . Идея состоит в том, что каждый символ pпредставляет собой непрерывную непустую подстроку, tкоторая находится рядом друг с другом, и pпредставляет их конкатенацию. Одинаковые символы соответствуют одинаковым подстрокам; например, шаблон aaпредставляет собой любой непустой квадрат (строка, полученная путем конкатенации более короткой строки к себе). Таким образом, шаблон aaможет соответствовать подстроке byebye, с каждым aсоответствием bye.

Выход

Если текст tсодержит подстроку, которая pсоответствует, то ваша продукция должна быть этой подстрокой с двоеточиями, :вставленными между строками, которые соответствуют символам p. Например, если у нас есть t = byebyenowи p = aa, то bye:byeэто приемлемый вывод. Может быть несколько вариантов для соответствующей подстроки, но вы должны вывести только один из них.

Если tне содержит подходящей подстроки, ваш вывод должен быть грустным лицом :(.

Правила и разъяснения

Разные символы pмогут соответствовать одинаковым подстрокам, поэтому p = abaмогут соответствовать строке AAA. Обратите внимание, что символы должны соответствовать непустым строкам; в частности, если pоно длиннее t, вывод должен быть :(.

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

Тестовые случаи

Дано в формате pattern text -> output. Обратите внимание, что могут существовать другие приемлемые результаты.

a Not -> N
aa Not -> :(
abcd Not -> :(
aaa rerere -> re:re:re
xx ABAAAB -> A:A
MMM ABABBAABBAABBA -> ABBA:ABBA:ABBA
x33x 10100110011001 -> 10:1001:1001:10
abcacb 0a00cca0aa0cc0ca0aa0c00c0aaa0c -> c:a0aa:0c:c:0c:a0aa
abccab 0a00cca0aa0cc0ca0aa0c00c0aaa0c -> a:a:0c0:0c0:a:a
abcbcab 0a00cca0aa0cc0ca0aa0c00c0aaa0c -> :(
abcbdcab 0a00cca0aa0cc0ca0aa0c00c0aaa0c -> 00:c:ca0aa0c:c:0:ca0aa0c:00:c
Zgarb
источник
1
Powerset всех подстрок? Почему нет!
orlp
1
@orlp Это только O(2^((n * (n + 1))/2)): P
ThreeFx
Что означает цифра в строке шаблона?
feersum
@feersum Это символ, поэтому он практически такой же, как и любой другой символ.
ThreeFx
@ThreeFx Я не уверен, потому что первый абзац относится только к «буквам» в шаблоне.
feersum

Ответы:

6

Python, 207 байт

import re
h=lambda x:"a"+str(ord(x))
def g(a,b):
 c,d="",set()
 for e in a:
  c+=["(?P<"+h(e)+">.+)","(?P="+h(e)+")"][e in d]
  d.add(e)
 f=re.search(c,b)
 return f and":".join(f.group(h(e))for e in a)or":("

Позвонить с g(pattern, string)

Использует reмодуль для выполнения большей части работы.

Номер один
источник
1

JavaScript (SpiderMonkey) (ES5.1), 198 байт

С тех пор, как ES6 был выпущен в июне 2015 года, я публикую версию кода ES5.1 вместе с эквивалентом ES6, но объявляю версию ES5.1 основным ответом.

Жадное совпадение, поэтому в первом случае возвращается «Не» вместо «N».

function(a,b){c=[o="indexOf"];r=a.split("");return(m=RegExp(r.map(function(i){return(e=c[o](i))>0?"\\"+e:(c.push(i),"(.+)")}).join("")).exec(b))?r.map(function(x){return m[c[o](x)]}).join(":"):":("}

Попробуйте онлайн!

JavaScript (Node.js) (ES6), 141 байт

a=>b=>(c=[o="indexOf"],r=[...a],m=RegExp(r.map(i=>(e=c[o](i))>0?"\\"+e:(c.push(i),"(.+)")).join``).exec(b))?r.map(x=>m[c[o](x)]).join`:`:":("

Попробуйте онлайн!

Принимает аргументы в карри синтаксисе: f(a)(b)

Объяснение (и не разгул):

function matchPattern(a, b) {                   // Main function
 var c = ["indexOf"];                           // Array used for the capturing groups
 var r = [...a];                                // Split the pattern first
 var m = RegExp(r.map(function(i) {             // Create the regex
  var e = c.indexOf(i);                         // Check if the character is found before
  if (e > 0)                                    // If so
   return "\\" + e;                             // Append the back reference to the regex
  else {                                        // If not
   c.push(i);                                   // Append the character to the array
   return "(.+)";                               // Append a capturing group to the regex
  }             
 }).join("")).exec(b);                          // Execute the regex
 if (m != null)                                 // If the pattern matches the string
  return r.map(function(x) {                    // Replace each letter
   return m[c.indexOf(x)];                      // With the corresponding substring
  }).join(":");                                 // And join them with ":"
 else                                           // If there is no match
  return ":(";                                  // Return ":("
}
Сиеру Асакото
источник
1

Брахилог , 35 байт

sᵗ~cᵗXlᵛ∧Xzdz≠ʰ∧Xt~ṇ{Ḷ∧":"|}ᵐ.∨":("

Попробуйте онлайн!

На не совсем маленьких входах очень медленно. Я на самом деле не делал шестой тестовый случай, но не из-за отсутствия попыток медленного. (Возможно, из-за грубого форсирования каждого раздела каждой подстроки, начиная с самой большой, а затем проверяя, совпадает ли она.) Принимает входные данные в виде списка [pattern,string].

Сокращенное и разделенное объяснение:

sᵗ~cᵗX

X - это шаблон в паре с разделом подстроки входной строки.

lᵛ

Узор и раздел имеют одинаковое количество элементов.

Xzdz≠ʰ

Никакие две уникальные pattern char, matched substringпары не имеют шаблонного символа. Таким образом, ни один символ шаблона не отображается на несколько подстрок, хотя несколько символов шаблона могут отображаться на одну подстроку.

Xt~ṇ{Ḷ∧":"|}ᵐ.∨":("

Вывод - это элементы раздела, объединенные двоеточиями, если что-то не может быть сделано, в этом случае :(вместо этого.

Монолитное объяснение:

                                       The input
 ᵗ  ᵗ                                  with its last element replaced with
  ~c                                   a list which concatenates to
s                                      a substring of it
     X                                 is X,
       ᵛ                               the elements of which all have the same
      l                                length.
        ∧                              And,
         X                             X
          z                            zipped
           d                           with duplicate pairs removed
            z                          and zipped back
              ʰ                        has a first element
             ≠                         with no duplicate values.
               ∧                       Furthermore,
                 t                     the last element of
                X                      X
                  ~ṇ                   with its elements joined by newlines
                    {      }ᵐ          where each character of the joined string
                     Ḷ                 is a newline
                      ∧                and
                          |            is replaced with
                       ":"             a colon
                          |            or is passed through unchanged
                             .         is the output.
                              ∨        If doing any part of that is impossible,
                                       the output is
                               ":("    ":(".
Несвязанная строка
источник
Прошло больше часа, и до сих пор не прошел шестой тестовый пример ... может, на самом деле он не работает? Он использует больше, чем свою долю процессора ...
Несвязанная строка
Хорошо, либо я недооценил временную сложность использования нескольких слоев жесткой грубой силы, либо это каким-то образом сломано, потому что он еще не выполнил шестой тестовый пример
Unrelated String
Я закрыл его сейчас, потому что если это займет три часа, я не уверен, сколько еще я буду ждать
Несвязанная Строка