- Implemente uma função que retorna o índice de uma sequência de caracteres seq dentro da string texto , e -1 se nada for encontrado (sem usar o operador in).
def busca_sequencia(texto, seq):
Por exemplo, busca_sequencia("introducao","cao") retorna 7.
busca_sequencia("introducao","dao") retorna -1.
busca_sequencia("introducao","introducao") retorna 0.
busca_sequencia("intro","introducao") retorna -1.
busca_sequencia("introducao","caoo") retorna -1.
def busca_sequencia(texto, seq):
Por exemplo, busca_sequencia("introducao","cao") retorna 7.
busca_sequencia("introducao","dao") retorna -1.
busca_sequencia("introducao","introducao") retorna 0.
busca_sequencia("intro","introducao") retorna -1.
busca_sequencia("introducao","caoo") retorna -1.
Passo 1
O enunciado pede para implementar uma função chamada
busca_sequencia que recebe duas strings: texto e seq. A função deve:- retornar o índice da primeira ocorrência de
seqdentro detexto(índice começando em); - retornar
se seqnão for encontrada; - não usar o operador
in.
Exemplos dados no enunciado:
busca_sequencia("introducao","cao")deve retornar. busca_sequencia("introducao","dao")deve retornar. busca_sequencia("introducao","introducao")deve retornar. busca_sequencia("intro","introducao")deve retornar. busca_sequencia("introducao","caoo")deve retornar.
Informações relevantes fornecidas:
- receberemos duas strings arbitrárias;
- comportamento quando não há correspondência: retornar
; - comportamento quando
seqé igual atexto: retornar índice; - proibido usar
in(não usar expressão comoif seq in texto:).
Passo 2
Definindo claramente os casos especiais (edge cases) que precisamos tratar antes de implementar:
- Se
seqfor a string vazia ("") — comportamento típico de funções de busca é retornar o índice(a substring vazia “aparece” no início). Vamos adotar isso: se seq == ""retornamos. - Se o comprimento de
seqfor maior que o comprimento detexto— impossível de encontrar, retornamos. - Caso geral:
0 < len(seq) <= len(texto)— precisamos procurar a primeira posição onde todos os caracteres deseqcasem com uma fatia detexto.
Esses casos garantem que não vamos acessar índices inválidos ao percorrer as strings.
Passo 3
Ideia do algoritmo (explicação didática, sem pular etapas):
- Vamos usar a técnica “janela deslizante” (sliding window): imaginamos uma janela de tamanho igual a
len(seq)que percorretextoda esquerda para a direita. - Em cada posição possível
da janela, comparamos caractere a caractere se texto[i + j] == seq[j]para todode até len(seq)-1. - Se todos os caracteres casarem, retornamos a posição
(primeira ocorrência). - Se chegarmos ao fim sem encontrar, retornamos
.
Por que isso funciona? Porque qualquer ocorrência de entre
e
seq em texto começa em alguma posição
len(texto) - len(seq) (inclusivo). Testando todas essas posições e comparando len(seq) caracteres cada, acharemos a primeira ocorrência quando ela existir.Passo 4
Explicando cada operação necessária no código e o porquê:
n = len(texto)em = len(seq)— guardamos comprimentos para não recalculá-los repetidamente.if m == 0: return 0— caso da substring vazia, explicação no Passo 2.if m > n: return -1— seseqé maior quetextonão cabe.for i in range(n - m + 1):— percorre todas as posições iniciais possíveis. Note querange(n - m + 1)gera valores deaté (inclusivo), exatamente as posições iniciais válidas. - Dentro do loop, usamos outro loop
for j in range(m):para comparar caractere a caractere. - Se encontrarmos um caractere diferente, interrompemos a verificação desta posição (
break) e avançamos para a próxima. - Se completarmos todos os
sem quebrar, significa que todos os caracteres casaram — retornamos . - Se o laço externo terminar sem retorno, retornamos
.
Vou explicar um detalhe: usamos uma variável booleana
match = True antes do loop interno. Se encontramos uma diferença, ajustamos match = False e damos break. Depois do loop interno verificamos if match: return i.Passo 5
Complexidade e justificativa prática:
- No pior caso, para cada posição
(até posições) comparamos até caracteres, então a complexidade é . - No caso médio, geralmente a execução é mais rápida porque boas divergências acontecem cedo; mas a solução é simples e eficiente o suficiente para uso em provas e para strings de tamanho moderado.
- Não usamos funções prontas de busca nem o operador
in, então atendemos à restrição do enunciado.
Passo 6
Implementação em Python (linha por linha comentada e explicada). Este código não usa o operador
in:def busca_sequencia(texto, seq):
# caso da substring vazia: conventionamente retornamos 0
if seq == “”:
return 0
n = len(texto) # comprimento de texto
m = len(seq) # comprimento da sequência procurada
# se seq é maior que texto, não cabe
if m > n:
return -1
# percorre todas as posições iniciais possíveis
for i in range(n - m + 1):
match = True
# compara caractere a caractere
for j in range(m):
if texto[i + j] != seq[j]:
match = False
break
# se todos os caracteres casaram, retornamos o índice i
if match:
return i
# se não encontramos em nenhuma posição, retornamos -1
return -1
# caso da substring vazia: conventionamente retornamos 0
if seq == “”:
return 0
n = len(texto) # comprimento de texto
m = len(seq) # comprimento da sequência procurada
# se seq é maior que texto, não cabe
if m > n:
return -1
# percorre todas as posições iniciais possíveis
for i in range(n - m + 1):
match = True
# compara caractere a caractere
for j in range(m):
if texto[i + j] != seq[j]:
match = False
break
# se todos os caracteres casaram, retornamos o índice i
if match:
return i
# se não encontramos em nenhuma posição, retornamos -1
return -1
Passo 7
Exemplos explicados passo a passo (mostrando como o algoritmo chega à resposta):
busca_sequencia("introducao","cao"):
texto = "introducao",seq = "cao".n = 10(índicesa ), m = 3.ipercorre deaté . - Para
i = 7: comparamostexto[7]comseq[0]⇒'c' == 'c'ok;texto[8]comseq[1]⇒'a' == 'a'ok;texto[9]comseq[2]⇒'o' == 'o'ok.
- Todos casaram, retornamos
. Isso bate com o exemplo.
busca_sequencia("introducao","dao"):
m = 3,ivai até. - Em todas as janelas de tamanho
nenhuma tem os três caracteres na ordem 'd','a','o'. - Logo retornamos
.
busca_sequencia("introducao","introducao"):
n = m = 10.range(n-m+1)érange(1)→ sói = 0.- Compara todos os caracteres; todos casam; retorna
.
busca_sequencia("intro","introducao"):
m = 10,n = 5. Comom > n, retornamosimediatamente.
busca_sequencia("introducao","caoo"):
m = 4,n = 10. Nenhuma janela de 4 caracteres tem'c','a','o','o'em sequência; retornamos.
Passo 8
Dicas para a prova (resumindo o que lembrar na hora):
- Pense em janela deslizante: você só precisa testar posições iniciais
a . - Faça sempre os checks de casos especiais primeiro (substring vazia, comprimento maior).
- Comparação caractere a caractere com dois loops é simples e aceita em provas sem usar funções prontas.
- Se precisar otimizar em problemas grandes, existem algoritmos mais avançados (KMP, Boyer–Moore), mas só use se a prova pedir otimização e você souber a ideia; caso contrário, a solução com dois loops costuma ser suficiente.
Resposta
def busca_sequencia(texto, seq):
if seq == “”:
return 0
n = len(texto)
m = len(seq)
if m > n:
return -1
for i in range(n - m + 1):
match = True
for j in range(m):
if texto[i + j] != seq[j]:
match = False
break
if match:
return i
return -1
if seq == “”:
return 0
n = len(texto)
m = len(seq)
if m > n:
return -1
for i in range(n - m + 1):
match = True
for j in range(m):
if texto[i + j] != seq[j]:
match = False
break
if match:
return i
return -1