Encontre a corda original, sem a repetição sem a repetição no meio

25

Às vezes acontece que, ao digitar uma frase, fico distraído e acabo digitando o mesmo par de palavras duas vezes duas vezes seguidas.

Para garantir que outras pessoas não se incomodem com isso, sua tarefa é escrever um programa que resolva esse problema!

Tarefa

Dada uma sequência de entrada (se for importante para o seu idioma, você pode assumir uma entrada apenas ASCII que não contém alimentações de linha.) str, Que contém em algum lugar no meio uma substring que ocorre duas vezes em sucessão imediata, retorne a sequência com uma instância desta substring removido.

No caso de múltiplas possibilidades, retorne a resposta mais curta possível (ou seja, escolha a substring de repetição consecutiva mais longa e remova essa).

No caso de várias substrings repetitivas consecutivas com o mesmo comprimento, remova a primeira (ou seja, a primeira encontrada ao ler a sequência da frente para trás).

Você pode presumir que a entrada está correta (ou seja, sempre contém uma subsequência consecutiva de substring), o que pode ajudar a diminuir o nível.


Exemplos

  1. Entrada: hello hello world-> Saída: hello world.
  2. Entrada: foofoo-> Saída: foo. (Então: Sim, a sequência pode consistir apenas na parte repetida duas vezes).
  3. Entrada: aaaaa-> Saída:, aaacomo a substring consecutiva de repetição mais longa está aqui aa.
  4. Entrada: Slartibartfast-> Esta não é uma entrada válida, pois não contém uma subsequência consecutiva consecutiva, portanto, você não precisa lidar com este caso.
  5. Entrada: the few the bar-> Esta é outra entrada inválida, pois a parte repetida deve seguir imediatamente a parte original. Nesse caso, thee thesão separados por outra coisa intermediária, portanto, esta entrada é inválida.
  6. Entrada: ababcbc-> Saída: abcbc. As duas substrings de repetição consecutivas mais longas possíveis são abe bc. Como abé encontrado anteriormente na cadeia, esta é a resposta correta.
  7. Entrada: Buffalo buffalo Buffalo buffalo buffalo buffalo Buffalo buffalo. Saída: Buffalo buffalo buffalo buffalo Buffalo buffalo. (A substituição realizada deve fazer distinção entre maiúsculas e minúsculas).
  8. Entrada: Sometimes it happens that while typing a sentence, I am distracted and I end up typing the same couple of words twice couple of words twice in succession.-> Saída: Sometimes it happens that while typing a sentence, I am distracted and I end up typing the same couple of words twice in succession.. Somente a substring de repetição consecutiva mais longa é removida.

Seu código deve ser o mais curto possível, já que esse é um , portanto a resposta mais curta em bytes vence. Boa sorte!

Qqwy
fonte
@manatwork Ao tomar a primeira frase, ou seja, Sometimes it happens that while typing a sentence, I am distracted and I end up typing the same couple of words twice couple of words twice in succession.como entrada, a saída deve ser Sometimes it happens that while typing a sentence, I am distracted and I end up typing the same couple of words twice in succession.. Somente a duplicação encontrada mais longa é removida.
Qqwy
1
Sugiro adicionar um teste com duas substituições possíveis, sendo que o segundo é mais longo que o primeiro. Eu suspeito que a maioria das respostas não vai passar que um :)
aross
caso de teste @aross 8 é exatamente isso :)
Qqwy
A menos que eu e meu código de teste estejam enganados, há apenas uma sequência repetida lá.
aross 8/03/2017
@aross existe um double pinhappens
Qqwy 9/17

Respostas:

8

Perl 6 , 40 bytes

{.subst: m:ex/(.*))>$0/.max(*.chars),''}

Tente

{
  .subst:             # substitute


    m                 # match
    :exhaustive
    /
      ( .* )          # any number of chars

      )>              # don't include the following in what is returned

      $0              # the first match again
    /.max( *.chars ), # find the first longest submatch


    ''                # substitute it with nothing
}
Brad Gilbert b2gills
fonte
8

Retina , 35 33 bytes

A contagem de bytes assume a codificação ISO 8859-1.

(?=(.+)(\1.*))
$2¶$`
O$#`
$.&
G1`

Experimente online!

Explicação

Como os mecanismos regex procuram correspondências da esquerda para a direita, não é trivial encontrar a correspondência mais longa, independentemente da posição. Isso pode ser feito com os grupos de balanceamento do .NET, mas o resultado é bastante desagradável:

1`((.)+)\1(?<=(?!.*((?>(?<-2>.)+).+)\3)^.*)
$1

Então imaginei que tentaria evitar isso usando outros recursos do Retina.

(?=(.+)(\1.*))
$2¶$`

Começamos aplicando essencialmente todas as substituições possíveis, uma em cada linha. Para fazer isso, correspondemos à posição na frente de uma partida (em vez da própria partida), para permitir correspondências sobrepostas. Isso é feito colocando o regex real em um lookahead. Essa cabeça de captura captura o restante, exceto a duplicata que queremos remover no grupo 2. Escrevemos novamente o grupo 2 (excluindo a duplicata), um avanço de linha e, em seguida, toda a entrada até a partida, o que nos dá basicamente uma nova linha para ser substituído.

No final, teremos uma linha para cada partida, com a duplicata correspondente removida. No final, também haverá a entrada completa novamente sem nenhuma substituição.

Agora que temos todas as substituições possíveis, queremos o resultado mais curto (o que corresponde à repetição removida mais longa).

O$#`
$.&

Então, primeiro classificamos as linhas por comprimento.

G1`

E então mantemos apenas a primeira linha.

Martin Ender
fonte
Uau, essa técnica de substituição é realmente inteligente!
Leo
6

Geléia , 22 19 bytes

-2 bytes graças a Dennis (evite uma inversão de argumento, remova um incremento sutilmente redundante)

ẋ2³wȧ+¥J
ẆÇ€LÐṀḢṬœp

Experimente online!

Programa completo (foi encontrado um erro por ÐṀnão agir com a aridade correta sobre as díades, que será corrigida em breve; embora eu não tenha certeza de que isso pode gerar códigos mais curtos aqui).

Quão?

Localiza a primeira das fatias mais longas da entrada, de modo que exista uma repetição na entrada e a remove da entrada.

ẋ2³wȧ+¥J - Link 1, removal indices for given slice if valid, else 0: slice, x
ẋ2       - repeat x twice, say y
  ³      - program input: s
   w     - index of first occurrence of y in s (1-based) or 0, say i
       J - range(length(x)): [1,2,3,...,length(x)]
      ¥  - last two links as a dyad
    ȧ    -     and (non-vectorising)
     +   -     addition: [1+i,2+i,3+i,...,length(x)+i] or 0
         - note: no need to decrement these since the last index will be the 1st index
         - of the repetition (thanks to Dennis for spotting that!)

ẆÇ€LÐṀḢṬœp - Main link: string, s
Ẇ          - all sublists of s (order is short to long, left to right, e.g. a,b,c,ab,bc,abc)
 Ç€        - call the last link (1) as a monad for €ach
    ÐṀ     - filter by maximal
   L       -     length
      Ḣ    - head: get the first (and hence left-most) one
       Ṭ   - untruth: make a list with 1s at the indexes given and 0s elsewhere
        œp - partition s at truthy indexes of that, throwing away the borders
           - implicit print
Jonathan Allan
fonte
6

JavaScript (ES6), 81 74 bytes

f=
s=>s.replace(/(?=(.+)\1)/g,(_,m)=>r=m[r.length]?m:r,r='')&&s.replace(r,'')
<input oninput=o.textContent=f(this.value)><pre id=o>

Editar: salvou 7 bytes roubando o m[r.length]truque de @ Arnauld .

Neil
fonte
5

PowerShell , 87 bytes

param($s)([regex](([regex]'(.+)\1'|% *hes $s|sort L*)[-1]|% Gr*|% V*)[1])|% Re* $s '' 1

Experimente online! (todos os casos de teste)

Explicação

Basicamente, partindo de dentro, corremos Matchescom o (.+)\1regex, para retornar todos os objetos correspondentes para a sequência especificada. A regex corresponde a qualquer sequência de caracteres que é seguida por ela mesma.

Em seguida, os objetos de correspondência resultantes são canalizados sortpara serem classificados por sua Lengthpropriedade (encurtados para curinga). Isso resulta em uma matriz de correspondências classificadas por comprimento, crescente e, portanto, indexe com [-1]para obter o último elemento (o mais longo). O valor dessa correspondência é a correspondência, não o grupo, portanto inclui a repetição; portanto, recuperamos o objeto Group ( |% Gr*) e, em seguida, o valor desse ( |% V*) para obter a maior sequência repetida. Coisa é que o objeto de grupo é na verdade uma matriz porque o grupo 0 é sempre a correspondência, mas eu quero o grupo real (1), portanto o valor resultante é realmente o valor s , portanto indexando para obter o segundo elemento [1]. Esse valor é convertido para um objeto regex e, em seguida, oReplaceO método é chamado na string original, substituindo por nada, e somente a primeira correspondência é substituída ( |% Re* $s '' 1).

briantist
fonte
5

Haskell , 101 bytes

A principal função é f, leva e retorna a String.

l=length
a=splitAt
f s|i<-[0..l s-1]=[p++t|n<-i,(p,(r,t))<-fmap(a$l s-n).(`a`s)<$>i,r==take(l r)t]!!0

Experimente online!

Quando eu comecei isso, eu importados Data.Liste usados maximum, tails, initse isPrefixOf. De alguma forma, isso se transformou nisso. Mas eu ainda consegui raspar 11 bytes ...

Notas

  • splitAt/ adivide uma string em um determinado índice.
  • s é a sequência de entrada.
  • ié a lista de números [0 .. length s - 1], -1é a splitAtsolução alternativa que se divide no final se for fornecido um índice muito grande.
  • né length smenos a meta atual de comprimento para a parte repetida, é escolhida dessa maneira, para que não tenhamos que usar duas listas de números e / ou a sintaxe detalhada da lista decrescente.
  • p, r, E tsão uma divisão threeway de s, com ro pretendido repetido parte. O fmapusa o (,) String Functorpara evitar uma variável para uma divisão intermediária.
  • !!0 seleciona o primeiro elemento da lista de correspondências.
Ørjan Johansen
fonte
4

Geléia , 23 21 bytes

ṚẆUẋ€2ẇÐf¹ṪðLHḶ+w@Ṭœp

Agradecemos a JonathanAllan por sua Ṭœpidéia, que salvou 2 bytes.

Experimente online!

Dennis
fonte
4

Mathematica, 63 60 59 bytes

4 bytes salvos devido a Martin Ender .

#&@@StringReplaceList[#,a__~~a__->a]~SortBy~{StringLength}&

Função anônima. Pega uma string como entrada e retorna uma string como saída.

LegionMammal978
fonte
Este não parece trabalho no exemplo 6 - ~SortBy~StringLengthordena cordas alfabeticamente se seus comprimentos são o mesmo ...
Não uma árvore
1
@ LegionMammal978 A correção mais curta é manter SortBye agrupar StringLengthuma lista para obter uma classificação estável.
Martin Ender
3

JavaScript (ES6), 70 bytes

s=>s.replace(s.match(/(.+)(?=\1)/g).reduce((p,c)=>c[p.length]?c:p),'')

Casos de teste

Arnauld
fonte
Falha aaaabaaab, mas bom uso de reduce.
Neil
2

Isso deve ser um comentário, mas não tenho reputação suficiente para comentar. Eu só quero dizer ao @Neil que seu código pode ser reduzido para 77 bytes. Você não precisa usar asserção direta na regex. Aqui está a versão reduzida:

s=>s.replace(/(.+)\1/g,(_,m)=>(n=m.length)>l&&(l=n,r=m),l=0)&&s.replace(r,'')
TRОLL
fonte
2
Olá, e bem-vindo ao PPCG! Você pode enviá-lo como sua própria resposta JavaScript! Se você quiser, posso editar sua postagem e mostrar como ela deve ficar.
NoOneIsHere 4/17
2
Eu preciso usar a afirmação direta para lidar com o caso de correspondências sobrepostas. aababé o exemplo mais curto de falha na sugestão.
305 Neil
0

C #, 169 bytes

(s)=>{var x="";for(int i=0;i<s.Length-2;i++){for(int l=1;l<=(s.Length-i)/2;l++){var y=s.Substring(i,l);if(s.Contains(y+y)&l>x.Length)x=y;}}return s.Replace(x+x,x);}

Explicação

(s) => {                // Anonymous function declaration    
    var x = "";         // String to store the longest repeating substring found
    for (int i = 0; i < s.Length - 2; i++) {               // Loop through the input string
        for (int l = 1; l <= (s.Length - i) / 2; l++) {    // Loop through all possible substring lengths
            var y = s.Substring(i, l);
            if (s.Contains(y + y) & l > x.Length) x = y;   // Check if the substring repeats and is longer than any previously found
        }
    }
    return s.Replace(x + x, x);    // Perform the replacement
}

Esta é a abordagem da força bruta: tente todas as subseqüências possíveis até encontrarmos a subseqüente repetição mais longa. Sem dúvida, o Regex é mais eficiente, mas lidar com o Regex em C # tende a ser bastante detalhado.

Extragorey
fonte
Bem-vindo ao PPCG! Todas as respostas precisam ser programas completos ou funções de chamada , sem ter certeza de trechos com entradas em variáveis ​​codificadas. Além disso, mostre a versão do código que você realmente contou com todo o espaço em branco desnecessário removido. Você sempre pode incluir a versão mais legível com recuo, além da versão totalmente golfe.
Martin Ender
0

PHP, 84 82 bytes

Nota: usa a codificação IBM-850.

for($l=strlen($argn);--$l&&!$r=preg_filter("#(.{0$l})\g-1#",~█╬,$argn,1););echo$r;

Execute assim:

echo 'hello hello world' | php -nR 'for($l=strlen($argn);--$l&&!$r=preg_filter("#(.{0$l})\g-1#",~█╬,$argn,1););echo$r;';echo
> hello world

Explicação

for(
  $l=strlen($argn);   # Set $l to input length.
  --$l   &&           # Decrement $l each iteration until it becomes 0.
  !$r=preg_filter(    # Stop looping when preg_filter has a result
                      # (meaning a successful replace).
    "#(.{0$l})\g-1#", # Find any character, $l times (so the longest
                      # match is tried first), repeated twice.
    ~█╬,              # Replace with $1: first capture group, removing the
                      # duplicate.
    $argn,
    1                 # Only replace 1 match.
  );
);
echo$r;               # Print the result of the (only) successful
                      # search/replace, if any.

Tweaks

  • 2 bytes salvos porque não há comprimento mínimo da substring repetida
aross
fonte