Encuentra subcadenas privilegiadas

8

Cuerdas privilegiadas

El conjunto de cadenas privilegiadas se define de forma recursiva de la siguiente manera.

  • Todas las cadenas de longitud 0 o 1 tienen privilegios.
  • Una cadena sde longitud de al menos 2 tiene privilegios, si existe una cadena privilegiada más corta tque se produce sexactamente dos veces, una como prefijo y otra como sufijo. Los sucesos superpuestos se cuentan como distintos.

Por ejemplo, las cadenas aa, aaay abason privilegiadas, pero aby aabno lo son.

Entrada

Una cadena alfanumérica.

Salida

Todas las subcadenas privilegiadas de la cadena de entrada, cada una exactamente, en cualquier orden. La salida se puede proporcionar en el formato de matriz nativo de su idioma (o el equivalente más cercano), o imprimir una subcadena por línea.

Hecho de la diversión

El número de cadenas en la salida siempre es exactamente length(s) + 1( fuente ).

Reglas

Ambas funciones y programas completos están permitidos. El conteo de bytes más bajo gana, y las lagunas estándar no se permiten.

Casos de prueba

Estos se ordenan primero por longitud y luego alfabéticamente, pero cualquier orden es aceptable.

"" -> [""]
"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"]

Tabla de clasificación

Aquí hay una tabla de clasificación por idioma, cortesía de Martin Büttner .

Para asegurarse de que su respuesta se muestre, comience con un título, usando la siguiente plantilla de Markdown:

# Language Name, N bytes

¿Dónde Nestá el tamaño de su envío? Si mejora su puntaje, puede mantener los puntajes antiguos en el título, tachándolos. Por ejemplo:

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

Mostrar fragmento de código

code-golf string Zgarb
fuente
¿Puede la salida estar separada por espacios o tiene que estar separada por nuevas líneas? (si imprime)
Sp3000
@ Sp3000 Tiene que ser líneas nuevas o, sin embargo, su idioma imprime una serie de cadenas.
Zgarb
2
¿Entonces nos pide que verifiquemos sus cadenas privilegiadas?
Imallett
¿Por qué una definición tan larga? ¿No podría haber escrito de manera equivalente "una cadena privilegiada es una cadena que comienza y termina con el mismo símbolo, dicho símbolo no aparece en ningún otro lugar de la cadena"? =)
Mints97
1
@ Mints97 La cadena más corta tpuede no ser un solo símbolo. Por ejemplo, aaaes una cadena privilegiada, ya que tiene aacomo prefijo y sufijo, y ocurre solo dos veces. Lo agregué como ejemplo.
Zgarb

Respuestas:

4

.NET Regex, 31 bytes

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

Las cadenas se capturan \1en cada partido.

Explicación

(?=                             # 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
fuente
5

CJam, 33 45 39 38 bytes

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

Digamos que se imprime sin una nueva línea final. Entonces, la nueva línea final significa una subcadena vacía ...

Explicación

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
fuente
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 voluminoso actualmente: me pregunto si es posible combinar el cheque y la generación de subcadenas de alguna manera ...

La lambda fes básicamente una is_privileged()función, que combina las tres condiciones en una comparación (la subcadena es privilegiada, aparece dos veces, es sufijo y prefijo).

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
fuente
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)

Esto recursivamente encuentra subcadenas privilegiadas, comenzando con las más cortas y agregándolas a un conjunto. El conjunto se usa para determinar si las subcadenas más largas tienen privilegios.

Desafortunadamente, es una función de un solo uso. Aquí hay un programa completo correspondiente ( 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
fuente
3

Pitón, 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 se demostró en el documento vinculado, hay un sufijo privilegiado único para cada prefijo de una cadena. Ese sufijo es de la forma p·u·pdonde pes la subcadena privilegiada más larga encontrada previamente, que es un sufijo del prefijo. (La búsqueda es el argumento de max, que en realidad encuentra la longitud de pporque era más fácil de hacer maxque longest). Una vez que pse encuentra, el sufijo en sí se forma buscando la segunda última aparición de pen el prefijo, usando rfindrestringido para no usar el último personaje Sabemos que funcionará, porque pes un sufijo encontrado previamente. (Una prueba más rigurosa del algoritmo puede derivarse del documento).

Estoy bastante seguro de que esto podría implementarse en tiempo lineal usando un árbol de sufijos, en lugar del algoritmo cúbico cuadrático utilizado anteriormente, pero el programa anterior es ciertamente lo suficientemente rápido en todos los casos de prueba y maneja una cadena de 2000 as en un poco menos de un segundo en mi laptop (no superpoder).

rici
fuente
2

Ruby, 87

Siento que hay una solución de expresión regular recursiva aquí en alguna parte, pero no soy muy buena en eso, así que aquí hay una función recursiva muy lenta y larga.

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

El algoritmo es más o menos el mismo que el de los grc , y se hace más lento (pero más corto) al no tener caracteres individuales de mayúsculas y minúsculas . Una cadena de un solo carácter puede considerarse privilegiada debido a que tiene la cadena vacía como prefijo, sufijo y en ningún otro lugar.

El otro truco interesante aquí es el uso de $'una variable mágica heredada de Perl que toma el valor de la cadena después de la coincidencia de expresión regular más reciente. Esto me da una forma corta de cortar el primer carácter de una cadena, aunque obtengo casi todos esos caracteres al tener que configurarlo en s[/./]lugar de s[0]. Lo uso de nuevo para verificar que la segunda coincidencia de subcadena ocurre al final de la cadena.

histocrat
fuente
1

J, 92 bytes

Toma un par de segundos en la entrada más larga.

pcomprueba si una cadena tiene privilegios (con recursividad), scomprueba cada subcadena con p.

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

Pruebas:

   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
fuente
1

JavaScript (ES6) 195

La función P verifica recursivamente que una cadena tiene privilegios.
La función F intenta cada subcadena contenida en la cadena dada. Las cadenas encontradas se almacenan como claves de una tabla hash para evitar duplicados.
Por fin, las claves se devuelven como salida.

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
fuente