Encontre Substrings Privilegiados

8

Cordas privilegiadas

O conjunto de cadeias de caracteres privilegiadas é definido recursivamente da seguinte maneira.

  • Todas as cadeias de comprimento 0 ou 1 são privilegiadas.
  • Uma sequência sde comprimento pelo menos 2 é privilegiada, se existir uma sequência privilegiada mais curta tque ocorra sexatamente duas vezes, uma vez como prefixo e outra como sufixo. Ocorrências sobrepostas são contadas como distintas.

Por exemplo, as cordas aa, aaae abasão privilegiados, mas abe aabnão são.

Entrada

Uma sequência alfanumérica.

Resultado

Todas as substrings privilegiadas da sequência de entrada, cada uma exatamente uma vez, em qualquer ordem. A saída pode ser fornecida no formato de matriz nativa do seu idioma (ou equivalente mais próximo) ou impressa uma subsequência por linha.

Fato engraçado

O número de strings na saída é sempre exatamente length(s) + 1( origem ).

Regras

São permitidas funções e programas completos. A contagem de bytes mais baixa vence e as brechas padrão não são permitidas.

Casos de teste

Eles são classificados primeiro pelo comprimento e depois em ordem alfabética, mas qualquer pedido é aceitável.

"" -> [""]
"a" -> ["","a"]
"abc" -> ["","a","b","c"]
"abcaaabccaba" -> ["","a","b","c","aa","cc","aaa","aba","abca","abcca","bccab","bcaaab","caaabc"]
"1010010110101010001101" -> ["","0","1","00","11","000","010","101","0110","1001","01010","10001","10101","010010","101101","0101010","1010101","01011010","10100101","1010001101","1101010100011","00101101010100","011010101000110"]
"CapsAndDigits111" -> ["","1","A","C","D","a","d","g","i","n","p","s","t","11","111","igi","sAndDigits"]

Entre os melhores

Aqui está uma tabela de classificação por idioma, cortesia de Martin Büttner .

Para garantir que sua resposta seja exibida, inicie-a com um título, usando o seguinte modelo de remarcação:

# Language Name, N bytes

onde Nestá o tamanho do seu envio. Se você melhorar sua pontuação, poderá manter as pontuações antigas no título, identificando-as. Por exemplo:

# Ruby, <s>104</s> <s>101</s> 96 bytes

Mostrar snippet de código

code-golf string Zgarb
fonte
A saída pode ser separada por espaço ou precisa ser separada por novas linhas? (se estiver imprimindo)
Sp3000 8/15
@ Sp3000 Tem de ser novas linhas ou, no entanto, a sua linguagem imprime uma série de cadeias de caracteres.
Zgarb 8/15
2
Então você está nos pedindo para verificar suas seqüências privilegiadas?
precisa saber é o seguinte
por que uma definição tão longa? Você não poderia ter escrito de forma equivalente "uma seqüência de caracteres privada é uma sequência que começa e termina com o mesmo símbolo; o referido símbolo não ocorre em nenhum outro lugar da sequência"? =)
Mints97
1
@ Mints97 A cadeia mais curta tpode não ser um símbolo único. Por exemplo, aaaé uma sequência privilegiada, pois possui aaprefixo e sufixo e ocorre apenas duas vezes. Eu adicionei como um exemplo.
Zgarb 9/02/2015

Respostas:

4

Regex .NET, 31 bytes

(?=(((?<=(\3\2|)).+?(?<=\3))*))

As strings são capturadas \1em cada partida.

Explicação

(?=                             # Lookahead. This makes it possible to catch overlapped
                                #   strings in \1.
    (                           # The captured group \1 for result.
        (                       # Match 0 or more occurrences.
            (?<=(\3\2|))        # Set \3 to the string from last \3 to the current position,
                                #   or an empty string for the first time.
            .+?(?<=\3)          # Match a shortest nonempty string so that the whole string
                                #   from the beginning to the current position ends with \3.
        )*
    )
)
jimmy23013
fonte
5

CJam, 33 45 39 38 bytes

l_,,\f>{(0{:U2$>2$2$#):T<+UT+T}g;\;N}%

Digamos que seja impresso sem uma nova linha à direita. Portanto, a nova linha à direita significa uma substring vazia ...

Explicação

l              " Read one line. ";
_,,            " Get an array of 0 to array length-1. ";
\f>            " Get all nonempty suffixes. ";
{              " For each suffix: ";
    (          " Extract the first character. Say the first character X and the rest Y. ";
    0          " Push U = 0. ";
    {          " Do: ";
        :U     " Set variable U. ";
        2$>    " Z = Y with first U characters removed. ";
        2$2$#  " Find X in Y, or return -1 if not found. ";
        ):T    " Increment and save it in T. ";
        <+     " Append the first T characters of Z to X. ";
        UT+    " U += T. ";
        T      " Push T. ";
    }g         " ...while T is nonzero. ";
    ;\;        " Discard U and Y. ";
    N          " Append a newline. ";
}%
jimmy23013
fonte
4

Python 2, 179 173 164 bytes

exec"f=lambda s:len(s)<2or any(s[1:-1].count(s[:n])<(s[:n]==s[-n:])==f(s[:n])for n%s);g=lambda s:filter(f,{''}|{s[i:j+1]for i%sfor j%s})"%((" in range(len(s))",)*3)

Bastante volumoso atualmente - gostaria de saber se é possível combinar a verificação e a geração de substring de alguma forma ...

O lambda fé basicamente uma is_privileged()função, combinando as três condições em uma comparação (a substring é privilegiada, aparece duas vezes, é sufixo e prefixo).

Expandido:

f=lambda s:len(s)<2or any(s[1:-1].count(s[:n])<(s[:n]==s[-n:])==f(s[:n])for n in range(len(s)))
g=lambda s:filter(f,{''}|{s[i:j+1]for i in range(len(s))for j in range(len(s))})
Sp3000
fonte
3

Python 3, 131 129 bytes

f=lambda s,p={''}:(len(s)<2or[f(s[1:]),f(s[:-1])]*any(s[:len(x)]==s[-len(x):]==x not in s[1:-1]for x in p))and p.add(s)or list(p)

Isso localiza recursivamente substrings privilegiados, começando pelos mais curtos e adicionando-os a um conjunto. O conjunto é então usado para determinar se substrings mais longos são privilegiados.

Infelizmente, é uma função de uso único. Aqui está um programa completo correspondente ( 145 bytes ):

p={''}
f=lambda s:(len(s)<2or[f(s[1:]),f(s[:-1])]*any(s[:len(x)]==s[-len(x):]==x not in s[1:-1]for x in p))and p.add(s)
f(input())
print(list(p))
grc
fonte
3

Python, 152 147 126 116 bytes

def n(s):
 w='';t=[w]
 for a in s:w+=a;t+=[w[w.rfind(w[-max(len(q)for q in t if w.endswith(q)):],0,-1):]]
 return t

Como demonstrado no artigo vinculado, há um sufixo privilegiado exclusivo para cada prefixo de uma sequência. Esse sufixo é da forma em p·u·pque pé a substring privilegiada mais antiga encontrada anteriormente, que é um sufixo do prefixo. (A pesquisa é o argumento para max, que na verdade encontra a extensão pporque era mais fácil de fazer do maxque isso longest.) Uma vez pencontrado, o sufixo é formado procurando pela segunda última ocorrência de pno prefixo, usando rfindrestrito para não usar o último caractere. Sabemos que isso funcionará, porque pé um sufixo encontrado anteriormente. (Uma prova mais rigorosa do algoritmo pode ser derivada do artigo.)

Tenho certeza de que isso poderia ser implementado em tempo linear usando uma árvore de sufixos, em vez do algoritmo cúbico quadrático usado acima, mas o programa acima é certamente rápido o suficiente em todos os casos de teste e lida com uma seqüência de 2000 as em um pouco menos de um segundo no meu laptop (não superpoderoso).

rici
fonte
2

Ruby, 87

Eu sinto que há uma solução regex recursiva aqui em algum lugar, mas eu não sou muito bom nisso, então aqui está uma função recursiva muito lenta e longa.

f=->s{s[/./]?(o=f[$']|f[s.chop];o.any?{|t|s[/^#{t}/]&&s[/.#{t}/]&&!$'[0]}&&o<<s;o):[s]}

O algoritmo é mais ou menos o mesmo que o grc , tornado mais lento (mas mais curto) por não apresentar caracteres únicos de maiúsculas e minúsculas. Uma cadeia de caracteres únicos pode ser considerada privilegiada por ter a cadeia vazia como prefixo, sufixo e em nenhum outro lugar.

O outro truque interessante aqui é o uso de $', uma variável mágica herdada do Perl que pega o valor da string após a última correspondência de expressão regular. Isso me dá uma maneira curta de cortar o primeiro caractere de uma string, embora eu ganhe quase todos esses caracteres ao configurá-lo em s[/./]vez de s[0]. Eu o uso novamente para verificar se a segunda correspondência de substring ocorre no final da string.

histocrata
fonte
1

J, 92 bytes

Leva alguns segundos na entrada mais longa.

pverifica se uma string é privilegiada (com recursão), sverifica cada substring usando p.

   p=.1:`(+./@:(($:@>@{.*((2=+/)*1={:)@{.@=)@(<\))~i.@#)@.(1<#)
   s=.3 :'~.a:,,(<@#~p)\.\y'

Testes:

   s 'CapsAndDigits111'
┌┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬───┬─┬──────────┬─┬──┬───┐
││C│a│p│s│A│n│d│D│i│g│igi│t│sAndDigits│1│11│111│
└┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴───┴─┴──────────┴─┴──┴───┘       

   input =. '';'a';'ab';'abc';'abcaaabccaba';'1010010110101010001101';'CapsAndDigits111'

   s each input
┌──┬────┬──────┬────────┬─────────────────────────────────────────────────────┬────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┬────────────────────...
│┌┐│┌┬─┐│┌┬─┬─┐│┌┬─┬─┬─┐│┌┬─┬─┬─┬────┬──┬───┬──────┬──────┬──┬─────┬─────┬───┐│┌┬─┬─┬───┬───┬──┬────┬──────┬────────┬──┬────┬──────┬────────┬─────┬─────┬───────┬───────┬──────────────┬───┬─────┬─────────────┬───────────────┬──────────┐│┌┬─┬─┬─┬─┬─┬─┬─┬─┬─┬...
││││││a││││a│b││││a│b│c││││a│b│c│abca│aa│aaa│bcaaab│caaabc│cc│abcca│bccab│aba││││1│0│101│010│00│1001│010010│10100101│11│0110│101101│01011010│10101│01010│1010101│0101010│00101101010100│000│10001│1101010100011│011010101000110│1010001101││││C│a│p│s│A│n│d│D│i│...
│└┘│└┴─┘│└┴─┴─┘│└┴─┴─┴─┘│└┴─┴─┴─┴────┴──┴───┴──────┴──────┴──┴─────┴─────┴───┘│└┴─┴─┴───┴───┴──┴────┴──────┴────────┴──┴────┴──────┴────────┴─────┴─────┴───────┴───────┴──────────────┴───┴─────┴─────────────┴───────────────┴──────────┘│└┴─┴─┴─┴─┴─┴─┴─┴─┴─┴...
└──┴────┴──────┴────────┴─────────────────────────────────────────────────────┴────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┴────────────────────...

   #@s each input NB. number of strings in outputs
┌─┬─┬─┬─┬──┬──┬──┐
│1│2│3│4│13│23│17│
└─┴─┴─┴─┴──┴──┴──┘

   # each input NB. input lengths
┌─┬─┬─┬─┬──┬──┬──┐
│0│1│2│3│12│22│16│
└─┴─┴─┴─┴──┴──┴──┘
randomra
fonte
1

JavaScript (ES6) 195

A função P verifica recursivamente que uma sequência de caracteres é privilegiada.
A função F tenta todas as subseqüências contidas na sequência especificada. As seqüências encontradas são armazenadas como chaves de uma tabela de hash para evitar duplicatas.
Por fim, as chaves são retornadas como saída.

F=a=>{
  P=(s,l=s.length,r=l<2,j=1)=>{
    for(;!r&&j<l;j++)s.indexOf(x=s.slice(0,j),1)+j-l||(r=P(x));
      return r
  };      
  for(o={'':l=i=0};a[i+l]||a[i=0,++l];)
    if(P(p=a.slice(i++,i+l)))
      o[p]=0;
  return[a for(a in o)]
}
edc65
fonte