Encontre padrões em strings

17

Nesse desafio, sua tarefa é localizar substrings com uma determinada estrutura.

Entrada

Sua entrada deve ser duas cadeias alfanuméricas não vazias, um padrão p e um texto t . A ideia é que cada caractere prepresente uma subcadeia não vazia contígua da tqual ocorra um ao lado do outro e prepresente sua concatenação. Caracteres idênticos correspondem a substrings idênticos; por exemplo, o padrão aarepresenta qualquer quadrado não vazio (uma sequência obtida concatenando uma sequência mais curta para si mesma). Assim, o padrão aapode corresponder à substring byebye, a cada acorrespondência bye.

Resultado

Se o texto tcontiver uma substring que pcorresponda, sua saída será essa substring, com dois pontos :inseridos entre as strings que correspondem aos caracteres de p. Por exemplo, se tivermos t = byebyenowe p = aa, então bye:byeé uma saída aceitável. Pode haver várias opções para a substring correspondente, mas você deve gerar apenas uma delas.

Se tnão contiver uma substring correspondente, sua saída será um rosto triste :(.

Regras e esclarecimentos

Caracteres diferentes de ppodem corresponder a substrings idênticos, portanto, p = abapodem corresponder à string AAA. Observe que os caracteres devem corresponder a cadeias não vazias; em particular, se pfor maior que t, a saída deve ser :(.

Você pode escrever um programa completo ou uma função e também pode alterar a ordem das duas entradas. A menor contagem de bytes vence e as brechas padrão não são permitidas.

Casos de teste

Dado no formato pattern text -> output. Observe que outras saídas aceitáveis ​​podem existir.

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
fonte
11
O conjunto de potência de todas as substrings? Por que não!
orlp
11
@orlp É apenas O(2^((n * (n + 1))/2)): P
ThreeFx 27/04/2015
O que significa um dígito na sequência padrão?
feersum
@feersum É um personagem, portanto é essencialmente o mesmo que qualquer outro personagem.
ThreeFx
@ThreeFx Não tenho certeza porque o primeiro parágrafo se refere apenas a "letras" no padrão.
feersum

Respostas:

6

Python, 207 bytes

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":("

Ligue com g(pattern, string)

Usa o remódulo para fazer a maior parte do trabalho.

O número um
fonte
1

JavaScript (SpiderMonkey) (ES5.1), 198 bytes

Desde que o ES6 foi lançado em junho de 2015, publico a versão ES5.1 do código junto com o equivalente ao ES6, mas declaro a versão ES5.1 como a principal resposta.

Correspondência gananciosa, portanto, o primeiro caso retorna "Não" em vez de "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(":"):":("}

Experimente online!

JavaScript (Node.js) (ES6), 141 bytes

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`:`:":("

Experimente online!

Adota os argumentos ao currying sintaxe: f(a)(b)

Explicação (e não destruída):

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 ":("
}
Shieru Asakoto
fonte
1

Braquilog , 35 bytes

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

Experimente online!

Em entradas não muito pequenas, muito lentas. Na verdade, eu não fiz o sexto caso de teste, mas não por falta de tentativa. (Provavelmente devido à força bruta de todas as partições de cada substring, começando pela maior e, em seguida, verificando se é uma correspondência.) Recebe a entrada como uma lista [pattern,string].

Explicação condensada e dividida:

sᵗ~cᵗX

X é o padrão emparelhado com uma partição de uma substring da sequência de entrada.

lᵛ

O padrão e a partição têm o mesmo número de elementos.

Xzdz≠ʰ

Dois pattern char, matched substringpares únicos não compartilham um caractere padrão. Ou seja, nenhum caractere padrão é mapeado para várias substrings, embora vários caracteres padrão possam ser mapeados para uma substring.

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

A saída são os elementos da partição unida por dois pontos, a menos que algo não possa ser feito; nesse caso, é :( .

Explicação monolítica:

                                       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
                               ":("    ":(".
String não relacionada
fonte
Já faz mais de uma hora e ainda não fez o sexto teste ... talvez não funcione? Ele está usando mais do que sua parte do processador ...
String não relacionada
Ok, quer eu subestimei a complexidade de tempo de utilização de várias camadas de força bruta duro, ou este é quebrado de alguma forma, porque ele ainda não fez o caso de teste sexta
Alheios Cordas
Eu desligá-lo agora, porque se leva três horas Eu não tenho certeza quanto tempo eu estou disposto a esperar
Alheios Cordas