Detector de substring repetida
Descubra se uma string é só um fragmento escrito várias vezes: ababab é ab três vezes e aaaa é a quatro vezes, enquanto aba não se repete. Você recebe a menor unidade e a contagem exata. Grátis no seu navegador.
- Grátis
- Funciona no seu navegador
- Sem cadastro
- Seus dados não saem do seu aparelho
Executar grátis
Exemplo resolvido
- Texto
- ababab
- Unidade de comprimento
- 2
- Quantidade
- 3
- Comprimento
- 6
Muitos problemas de entrevista e checagens de limpeza de dados fazem uma pergunta simples: esta string é apenas um fragmento mais curto escrito várias vezes? Strings como ababab, aaaa e xyzxyzxyz são construídas assim; abc e aba não. Este detector de padrão de substring repetida aceita um único campo de texto não vazio, executa uma análise determinística de borda KMP (maior prefixo-sufixo próprio) e devolve a menor unidade repetitiva junto com a contagem exata de repetições. Não há chamada de rede, aleatoriedade nem dependência de relógio — apenas aritmética de strings que você pode reexecutar byte a byte.
O que é um padrão de substring repetida e como a unidade é escolhida
Uma string tem um padrão de substring repetida quando é igual a alguma unidade não vazia escrita de ponta a ponta pelo menos duas vezes, sem caracteres sobrando. Por exemplo, ababab é a unidade ab escrita três vezes, aaaa é a unidade a escrita quatro vezes e xyzxyz é a unidade xyz escrita duas vezes. O detector sempre devolve a menor unidade desse tipo: se uma string pode ser recoberta tanto por ab quanto por abab, a resposta é ab com uma contagem maior, não o candidato mais longo.
Quando nenhuma unidade mais curta recobre o comprimento total, a string é informada como não repetida: unit é igual ao texto original e count é igual a um. O teste clássico em tempo linear constrói a tabela KMP do maior prefixo-sufixo próprio para a string de comprimento n, define period como n menos o comprimento da borda final e verifica se period divide n e é estritamente menor que n.
Se ambas as condições valem, a unidade é o prefixo de comprimento period e a contagem é n dividido por period. Isso coincide com a varredura por força bruta de divisores que tenta cada comprimento de um até o piso de n sobre dois, mas permanece O(n) e nunca depende de relógios flutuantes ou sementes aleatórias.
Strings de um único caractere e resultados vazios de validação são tratados de forma explícita: comprimento um não pode ser uma repetição não trivial, e texto vazio ou ausente é rejeitado antes de qualquer trabalho LPS.
Onde um detector de padrão repetido gera valor
Preparação para entrevistas e cursos de algoritmos usam este problema para ensinar bordas, períodos e argumentos de divisores; um detector ao vivo permite que estudantes verifiquem ababab versus aba sem montar tabelas LPS à mão sob pressão de tempo. Professores e autores de LMS precisam de um oráculo determinístico que devolva tanto o sinal booleano do padrão quanto a unidade concreta, para que corretores automáticos aceitem qualquer explicação correta que nomeie o mesmo menor fragmento.
Pipelines de qualidade de dados marcam colunas que parecem repetições acidentais de copiar e colar (SKU SKU SKU, yesyesyes) antes que poluam índices de busca ou analytics. Demonstrações de compressão e codificação ilustram estrutura no estilo run-length sem pretender ser um compressor completo: mostrar que xyzxyzxyz são três cópias de xyz costuma bastar para um slide de aula. Validação falha não consome saldo.
Casos de uso
Prática de entrevistas e algoritmos
Verifique se uma string é um padrão repetido não trivial e nomeie a menor unidade e a contagem em relação a soluções de livro com KMP e divisores.
Qualidade de dados e colagens duplicadas
Sinalize células ou tokens que são repetições puras de um fragmento mais curto antes de entrarem em índices, catálogos ou analytics.
Perguntas frequentes
Como detecto um padrão de substring repetida?
Envie uma string não vazia no campo text. Quando a string não é uma repetição não trivial, unit é a string completa e count é 1.
O que é a menor unidade repetitiva?
É o menor prefixo não vazio que recobre a string inteira sem resto. Para ababab a unidade é ab (não abab). Para aaaa a unidade é a.
Qual algoritmo o detector usa?
Um teste de período KMP do maior prefixo-sufixo próprio (LPS): se period = n - lps[n-1] divide n e é menor que n, a unidade é o prefixo desse comprimento. Equivale a tentar cada comprimento divisor, mas em tempo linear.
O que recebo quando a string não se repete?
Uma resposta normal, não um erro: o resultado indica que não há repetição, a unidade é a string inteira e a contagem é um. Strings comuns sem repetição, como abc, são tratadas do mesmo jeito.
A unidade precisa cobrir a string inteira?
Sim. Uma string só conta como repetida quando a unidade, escrita pelo menos duas vezes seguidas, a cobre sem sobrar nenhum caractere. Por isso aba não é uma repetição, mesmo começando e terminando com a.
Ferramentas relacionadas
Para desenvolvedores — acesso via API
Tudo nesta página está disponível via API. Esta seção é para equipes que querem integrar a ferramenta aos próprios sistemas; quem não precisa disso pode simplesmente usar a ferramenta acima.
Endpoint
Autenticação por token Bearer. Um único POST coloca a tarefa na fila; o resultado chega por webhook ou link assinado.
Chame do seu código
curl -X POST https://api.kit.forhosting.com/dev/repeated-substring \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"text":"ababab"}'const res = await fetch("https://api.kit.forhosting.com/dev/repeated-substring", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"text": "ababab"
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/dev/repeated-substring",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"text": "ababab"
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/dev/repeated-substring", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"text":"ababab"}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"text":"ababab"}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/dev/repeated-substring", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)Exemplo de requisição
{
"text": "ababab"
}Exemplo de resposta
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "dev.repeated_substring",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}A API é assíncrona: cada chamada devolve um task_id na hora. Se preferir polling, consulte o status a até 1 requisição por segundo.
Preço
Preço publicado, sem tokens nem créditos escondidos. Tarefa que falha não é cobrada.
Erros
| HTTP | Código | O que significa |
|---|---|---|
401 | unauthorized | Token ausente ou inválido. Confira o header Authorization. |
402 | insufficient_balance | Saldo insuficiente para esta tarefa. Faça uma recarga e tente de novo. |
404 | unknown_type | Esse tipo de tarefa não existe. Confira o campo type no catálogo. |
429 | rate_limited | Muitas requisições em pouco tempo. Espere um instante e tente de novo. |
Notas técnicas
Quando nenhuma unidade mais curta recobre a string inteira, a resposta marca is_repeated como false, define unit como o texto completo e count como um, para que quem chama sempre obtenha um contrato estável.
O que é um padrão de substring repetida e como a unidade é escolhida
Esse contrato é mais amigável a pipelines do que um erro rígido em não padrões, porque quem chama pode ramificar em is_repeated sem tratar strings únicas ordinárias como entrada inválida.
Contrato de entrada, campos de resposta e comportamento de erro
Exemplo: aaaa produz unit a e count quatro. Mantenha as entradas abaixo do teto de caracteres documentado; colagens grandes demais falham com uma mensagem de limite explícita em vez de um corte silencioso truncado. Envie por POST um corpo JSON com um campo text obrigatório contendo uma string não vazia. Os aliases input, string, value, s e source são aceitos para que formulários de consulta, planilhas e wrappers de SDK tipados reutilizem o mesmo contrato sem renomear colunas. Números finitos e bigints são convertidos primeiro em string, de modo que um código de produto digitado como número puro ainda é analisado com limpeza; booleanos, objetos simples e arrays são rejeitados para que um corpo JSON enganoso não se torne a palavra true nem um dump de objeto pouco útil. Strings vazias e text ausente falham com invalid_input e não são cobrados. Em caso de sucesso o corpo inclui text (eco da string analisada), is_repeated (true quando count é pelo menos dois), unit (o menor fragmento repetitivo, ou a string completa quando não se repete), unit_length, count, length do texto original e method fixo em kmp_period para logs e pipelines multi-ferramenta. Exemplo: ababab produz unit ab, unit_length dois, count três, is_repeated true. Exemplo: abc produz unit abc, count um, is_repeated false. Combine a execução gratuita no navegador nesta página com a API cobrada quando você precisar da mesma unidade e contagem dentro de CI, scripts de correção ou workers de borda sem reimplementar KMP por conta própria.
Onde um detector de padrão repetido gera valor
Como a implementação é parse pura de nível A, cada chamada bem-sucedida custa o preço base publicado US$ 0,002, sem tokens de modelo e sem rede de saída.
Casos de integração
Correção automática LMS e deveres
Avalie itens de substring repetida com um oráculo determinístico que devolve unit, count e is_repeated para comparação estável.
Perguntas técnicas
E se a string não for repetida?
A chamada ainda tem sucesso: is_repeated é false, unit é igual ao texto original e count é 1. Apenas text ausente ou vazio é invalid_input.
Quanto custa o detector de padrão de substring repetida?
A ferramenta do navegador é gratuita. Solicitações API usam saldo pré-pago do KIT a US$ 0,002 por chamada bem-sucedida; entrada inválida não é cobrada.