Verifique se uma sequência é totalmente composta da mesma substring

24

Isto é retirado desta questão (com permissão de curso). Vou citar:

Crie uma função que use uma string e ela retorne true ou false com base em se a entrada consiste em apenas uma sequência de caracteres repetida. O comprimento de uma determinada sequência é sempre maior que 1 e a sequência de caracteres deve ter pelo menos uma repetição.

Alguns exemplos:

'aa' //true
'aaa' //true
'abcabcabc' //true
'aba' //false
'ababa' //false
'weqweqweqweqweqw' // false

Especificamente, a verificação de uma string estritamente composta por substrings repetidos ( Update ) pode gerar qualquer representação verdadeira ou falsa, mas nenhum erro de saída, por favor. Strings estritamente alfanuméricos. Caso contrário, regras de golfe com código padrão. Este é o Code Golf, portanto, a resposta mais curta em bytes para cada idioma vence.

code-golf decision-problem ouflak
fonte
4
Hum, eu ia fechar esse desafio como um idiota daquele , mas notei que o outro pontua na contagem de caracteres. Então, talvez devêssemos fechar a outra (que também tem uma resposta aceita) como uma burra dessa.
Erik the Outgolfer
Vamos continuar esta discussão no chat .
Erik the Outgolfer

Respostas:

11

Braquilog , 4 3 bytes

ġ=Ṁ

Experimente online!

Explicação

ġ=Ṁ    Implicit input, say "abcabc"
ġ      Split into chunks of equal lengths (except maybe the last one): ["abc","abc"]
 =     Apply the constraint that all of the chunks are equal,
  Ṁ    and that there are multiple of them.

O programa imprime true.se as restrições podem ser satisfeitas e, false.se não.

Zgarb
fonte
Eu estava apenas tentando conseguir algo como ~j↙ou =Ṁctrabalhar antes de perceber que você postou isso há uma hora
String não relacionada
4
Ah, sim, isso poderia ser um byte mais curto:ġ=Ṁ
String não relacionada
( Ṁé uma variável restrita a ser uma lista de dois ou mais elementos)
String não relacionada
11
@UnrelatedString Ótimo, obrigado! Não pensei em verificar a página wiki das variáveis.
Zgarb 25/04
11
Muitas ótimas respostas, e a resposta da LUA tem um lugar especial no meu coração. A resposta de Arnauld é particularmente agradável, já que a pergunta original em que eu baseei isso (e não o idiota) é realmente marcada como Javascript. Principalmente selecionando este apenas porque parece ser o mais curto para todos os idiomas e, como esta é minha primeira pergunta, recebo um distintivo.
ouflak
19

JavaScript (ES6), 22 bytes

Retorna um valor booleano.

s=>/^(.*)\1+$/.test(s)

Experimente online!

Sem uma expressão regular,  33  29 bytes

Retorna null(falsy) ou um objeto (truthy).

s=>(s+s).slice(1,-1).match(s)

Experimente online!

Nota: tecnicamente, s é convertido em uma expressão regular para match () , portanto o título acima é uma mentira.

Arnauld
fonte
9

grep, 19

grep -qxE '(.+)\1+'

Teste

while read; do 
  <<<"$REPLY" grep -qxE '(.+)\1+' && t="true" || t="false"
  echo "$REPLY: $t"
done < infile

Saída:

aa: true
aaa: true
abcabcabc: true
aba: false
ababa: false
weqweqweqweqweqw: false
Thor
fonte
9

Japonês , 6 bytes

²é ¤øU

Guardou um byte graças a @Shaggy

Experimente online!

        Implicit input, stored in variable 'U'
²       U+U, "abcabc" -> "abcabcabcabc"
 é      Rotate 1 char to the right "abcabcabcabc" -> "cabcabcabcab"
   ¤    Remove first two chars, "cabcabcabcab" -> "bcabcabcab"
    øU  Check if U is in the above
Forma de Ignorância
fonte
Agradável :) Você pode substituir o p<space>por ²para salvar um byte.
Shaggy
9

Java, 25 24 bytes

-1 byte graças a Olivier Grégoire!
Resposta regex chata

s->s.matches("(.+)\\1+")

Experimente online!

É apenas 1 byte a mais do que a resposta python aaaaa , estou empatado agora :)

Benjamin Urquhart
fonte
3
Você pode remover a final, $pois o matchesmétodo é uma correspondência exata, não uma correspondência de substring por padrão.
Olivier Grégoire
Eu esqueci matchesadiciona seu próprio $ao regex. Obrigado!
Benjamin Urquhart
7

Excel, 26 bytes

=FIND(A1,A1&A1,2)<=LEN(A1)

Entradas de A1, saídas para qualquer célula que você colocar nesta fórmula.

Sophia Lechner
fonte
Você pode salvar 4 bytes se definir um nome de intervalo de uma letra (por exemplo A) e definir isso como sua entrada.
i_saw_drones 24/04
@i_saw_drones - acho que isso não é permitido pelas regras de E / S padrão: aqui está um link para a meta resposta que se aplicaria a esse método; está atualmente em -36 votos.
Sophia Lechner
Desculpas que eu não tinha visto naquele post, apesar de pensar nisso, A1também não são uma "variável", pois contém o valor de entrada? :)
i_saw_drones 24/04
11
Eu me sentiria assim se estivesse fazendo algo especial com o fato de ser o A1 especificamente, como se eu confiasse de alguma forma no ROW (_) sendo 1. Como é, porém, é apenas a maneira mais natural de fornecer uma função do Excel com uma entrada arbitrária.
Sophia Lechner
7

R , 28 bytes

grepl("(.+)\\1+$",scan(,''))

Experimente online!

Versão simples do Regex. R é (às vezes) muito semelhante ao Python, então isso é semelhante à resposta regex do TFeld no Python 2, embora mais curta!

Pergunta (se alguém souber a resposta)

Ainda estou confuso por que isso funciona, pois a substring pode ter qualquer tamanho e sempre funcionará, e ainda funciona quando adiciono uma letra à frente de uma string válida, como "cABABABABAB". Se eu pessoalmente ler o regex, vejo (.+), que captura qualquer grupo de qualquer tamanho. E depois\\1+$ que repete o grupo capturado inúmeras vezes até o final.

Então, por que ele não captura apenas "AB" e descobre que é repetido até o final da string, principalmente porque não há nenhuma restrição especificada sobre onde a substring pode começar?

Sumner18
fonte
11
Interessante, isso parece ser um bug no mecanismo de expressão regular de R. A adição da opção perl=TRUEfaz com que ela corresponda ao cABABAB, como seria de esperar. A execução grep -E '(.*)\1+$'no bash também corresponde ao cABABAB, mesmo que grep -Euse ERE, o mesmo tipo de expressão regular R deve oferecer suporte.
Grimmy 25/04
2
Meu palpite é que essa é uma otimização aplicada incorretamente. Alterar .+no início de um padrão para ^.+é uma otimização importante, mas se a .+captura de dentro estiver parecendo, ela deixa de ser válida.
Grimmy 25/04
6

Geléia ,  5  4 bytes

Vejo agora que a melhor maneira é seguir o método do xnor !

Ḋ;Ṗw

Um link monádico que aceita uma lista de caracteres e gera um número inteiro - o menor comprimento possível de uma fatia repetida ou zero, se não houver nenhum. Observe que zero é falsey, enquanto números diferentes de zero são verdadeiros no Jelly.

Experimente online!

Quão?

Ḋ;Ṗw - Link: list of characters, S   e.g. "abcabcabc"   or "abababa"
Ḋ    - dequeue S                           "bcabcabc"       "bababa"
  Ṗ  - pop from S                         "abcabcab"       "ababab"
 ;   - concatenate                "bcabcabcabcabcab"       "bababaababab"
   w - first index of sublist     3  ^---here!             0  (not found)
Jonathan Allan
fonte
4

Wolfram Language (Mathematica) , 24 23 bytes

StringMatchQ[x__..~~x_]

Experimente online!

StringMatchQ[           (*a function that checks if its input (string) matches:*)
             x__..      (*a sequence of one or more characters, repeated one or more times*)
                  ~~x_] (*and one more time*)
attinat
fonte
3

PowerShell, 23 24 bytes

+1 byte para corresponder totalmente às regras

"$args"-match"^(.+)\1+$"

Experimente online!

Muito chato. Com base nas outras respostas do Regex. Felizmente, o PowerShell não usa \como caractere de escape!

Gabriel Mills
fonte
ele retorna trueparaaabcabc
mazzy 25/04
11
@mazzy apenas corrigido!
Gabriel Mills
3

C # (compilador interativo do Visual C #) , 70 bytes

adaptação descarada do xnor ( 46 bytes )

s=>(s+s).Substring(1,s.Length*2-2).Contains(s)

Minha solução não Regex:

s=>s.Select((x,y)=>y).Count(z=>s.Replace(s.Substring(0,z+1),"")=="")>1

Explicação:

Substitua todas as subseqüências possíveis iniciadas no índice 0 por uma sequência vazia. Se o resultado for uma sequência vazia, a sequência será totalmente composta dessa substring. Como isso inclui avaliar a sequência inteira com ela mesma, a quantidade de resultados esperados deve ser maior que 1.

Exemplo: abcabc

Possíveis substrings começando no índice 0:

'a', 'ab', 'abc', 'abca', 'abcab', 'abcabc'

Se os substituirmos por cadeias vazias

Substring          Result

'a'         =>     'bcbc'
'ab'        =>     'cc'
'abc'       =>     ''
'abca'      =>     'bc'
'abcab'     =>     'c'
'abcabc'    =>     ''

Como existe uma substring diferente de 'abcabc' que retorna uma string vazia, a string é totalmente composta de outra substring ('abc')

Experimente online!

Innat3
fonte
3

Python 3 , 62 60 56 54 bytes

-4 bytes thanx ao ArBo

lambda s:s in(len(s)//l*s[:l]for l in range(1,len(s)))
  1. Iterar sobre todos os prefixos possíveis na string.
  2. Tente criar a string fora do prefixo.
  3. Retorne se isso é bem-sucedido com qualquer prefixo.

Experimente online!

movatica
fonte
11
Boa resposta! O f=pode ser descartado; funções anônimas são geralmente permitidas. Além disso, alternando para o Python 2 e verificando a associação de uma lista em vez da anyconstrução, você pode obter 55 bytes
ArBo
11
Boa captura com a associação da lista, thanx! Não mudarei para o Python 2, pois é como mudar a linguagem, o que obviamente não é o ponto aqui;) Além disso, existe uma maneira conveniente de testar uma função anônima no TIO, mantendo a contagem de bytes?
movatica 26/04
11
@movatica No cabeçalho, coloque `f =` (\ é o caractere de continuação de linha em python)
Artemis suporta Monica
Irritantemente, \ também é um caractere de escape. Aqui, sem formatação de código, é o que você deve colocar no cabeçalho: f = \
Artemis suporta Monica
2

Japonês , 10 bytes

Retorna um número positivo se for verdade e 0 se falsey. Se você quiser uma saída bool, basta adicionar -¡sinalizador

å+ k@rXÃÊÉ

å+ k@rXÃÊÉ      Full program. Implicit input U.
                    e.g: U = "abcabcabc"
å+              Take all prefixes 
                         U = ["a","ab","abc","abca","abcab","abcabc","abcabca","abcabcab","abcabcabc"]
   k@           Filter U by:
     rXÃ        Values that return false (empty string)
                when replacing each prefix in U
                e.g: ["bcbcbc","ccc","","bcabc","cabc","abc","bc","c",""]
                                take ↑                             and ↑
                     U = ["abc","abcabcabc"]
         ÊÉ     Get U length and subtract 1. Then return the result

Experimente online!

Luis felipe De jesus Munoz
fonte
2

Casca , 6 bytes

Ṡ€ȯhtD

Experimente online!

Sinto que esse é um byte a mais do que o ideal, mas não consegui encontrar um arranjo que tornasse a composição explícita ȯdesnecessária.

Explicação

Ṡ€      Find the argument in the result of applying the following function to the argument
  ȯhtD  Duplicate the argument, then remove the first and last elements.
Sophia Lechner
fonte
2
€htD¹evita o ȯ.
Zgarb 24/04
Isso é fantástico! Eu tinha pensado, λ€htD¹mas não sabia que lambdas seriam adicionadas implicitamente
Sophia Lechner
2

Mathematica 11.x, 74 bytes

{}!=StringCases[#,StartOfString~~x__/;(x!=#&&StringReplace[#,x->""]=="")]&

onde, por toda parte # representa a sequência de entrada e

StringCases[#,<pattern>]

localiza substrings da string de entrada que correspondem ao padrão

StartOfString~~x__/;(x!=#&&StringReplace[#,x->""]=="")

Esse padrão requer correspondências, x deve começar no início da sequência e deve satisfazer a condição de que (1) a correspondência não é a sequência de entrada inteira e (2) se substituirmos as ocorrências da correspondência na sequência de entrada pela sequência vazia nós obtemos a string vazia. Por fim, comparando a lista de correspondências com a lista vazia,

{}!=

é True se a lista de correspondências não for vazia e Falsese a lista de correspondências estiver vazia.

Casos de teste:

{}!=StringCases[#,StartOfString~~x__/;(x!=#&&StringReplace[#,x->""]=="")]&["aa"]
(*  True  *)
{}!=StringCases[#,StartOfString~~x__/;(x!=#&&StringReplace[#,x->""]=="")]&["aaa"]
(*  True  *)
{}!=StringCases[#,StartOfString~~x__/;(x!=#&&StringReplace[#,x->""]=="")]&["abcabc"]
(*  True  *)

e

{}!=StringCases[#,StartOfString~~x__/;(x!=#&&StringReplace[#,x->""]=="")]&["aba"]
(*  False  *)
{}!=StringCases[#,StartOfString~~x__/;(x!=#&&StringReplace[#,x->""]=="")]&["ababa"]
(*  False  *)
{}!=StringCases[#,StartOfString~~x__/;(x!=#&&StringReplace[#,x->""]=="")]&["weqweqweqweqweqw"]
(*  False  *)
Eric Towers
fonte
2

Python 3, 84 bytes

import textwrap
lambda s:any(len(set(textwrap.wrap(s,l)))<2 for l in range(1,len(s)))

Utiliza textwrap.wrap(graças a esta resposta ) para dividir a cadeia em pedaços de comprimento npara testar cada comprimento possível de substring repetido. As partes divididas são comparadas entre si adicionando-as a um conjunto. Se todas as peças forem iguais e o conjunto tiver comprimento 1, a sequência deverá ser repetida. Eu usei em <2vez de, ==1porque ele salva um byte, e o comprimento da string de entrada foi garantido maior que zero.

Se não houver nquais substrings repetidos de comprimento ncompõem a cadeia inteira, retorne false para toda a função.

Delya Erricson
fonte
2

05AB1E , 5 bytes

O método xnor da pergunta anterior também parece ótimo no 05AB1E.

«¦¨så

Experimente online! ou como um conjunto de testes

Explicação

«       # append input to input
 ¦¨     # remove the first and last character of the resulting string
   så   # check if the input is in this string
Emigna
fonte
11
Claro ... Eu estava prestes a responder 05AB1E quando vi que não havia nenhum. O colega me fez algumas perguntas e falou sobre suas férias. Olho para a tela: uma nova resposta. Tada, bata novamente XD
Kevin Cruijssen 25/04
@KevinCruijssen: Isso é típico. Já aconteceu comigo
várias
2

Limpar \ limpo , 73 bytes

Não usa regex.

import StdEnv,Data.List
$s=or[isPrefixOf s(cycle t)\\t<-tl(tails s)|t>[]]

Experimente online!

Define $ :: [Char] -> Bool.
Verifica se a string especificada é um prefixo da repetição de qualquer sub-string retirada do final.

Furioso
fonte
2

C ++ (gcc) , 36 bytes

#define f(x)(x+x).find(x,1)<x.size()

Experimente online!

Outra porta da solução do xnor. Usa uma macro para expandir o argumento na expressão. O argumento é assumido como sendo do tipo std::string.

jxh
fonte
1

Variável QlikView, 27 bytes

Isso deve ser definido como uma variável, que permite passar parâmetros, por exemplo, $1como seu valor de entrada.

Ele retorna 0ou -1(equivalente à TRUE()função do QlikView ).

=substringcount($1&$1,$1)>2
i_saw_drones
fonte
1

Rápido, 196 bytes

func r(s:String)->Bool{guard let k=s.dropFirst().firstIndex(where:{$0==s.first}) else{return false};let v=s[...k].dropLast();var w=v;while s.hasPrefix(w) && s.count>=(w+v).count{w+=v};return s==w}

Experimente online!

onnoweb
fonte
Eu não uso o Swift, mas tenho certeza de que espaço em branco extra pode ser removido
Benjamin Urquhart
193 bytes usando a sugestão de @ benjamin.
Artemis apoia Monica em
@ArtemisFowl ou mesmo 123 bytes
Roman Podymov
1

T-SQL, 47 bytes

Usando o método do @ Xnor :

DECLARE @ varchar(max)='ababab'

PRINT sign(charindex(@,left(@+@,len(@)*2-1),2))

Mantendo a resposta antiga, pois contém um bom jogo de golfe (67 bytes):

DECLARE @y varchar(max)='abababa'

,@ INT=0WHILE
replace(@y,left(@y,@),'')>''SET
@+=1PRINT @/len(@y)^1

Explicação: Este script está tentando repetidamente substituir a entrada '@y' pelos primeiros caracteres '@' da entrada '@y' por nada, enquanto aumenta '@'.

se você substituir 'ab' em 'ababab' por nada, você terá uma string vazia

Eventualmente, o resultado ficará vazio. Se isso acontecer quando a variável de loop for igual ao comprimento do varchar, o critério será falso / 0 porque '@' = len (@y) (não houve varchar repetido).

iif(@=len(@y),0,1)

pode ser jogado neste

@/len(@y)^1

porque o comprimento de '@y' não pode ser 0 e '@' nunca excederá o comprimento @y.

Experimente online

t-clausen.dk
fonte