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

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 seq dentro de texto (índice começando em 0);
  • retornar -1 se seq não for encontrada;
  • não usar o operador in.
Exemplos dados no enunciado:
  • busca_sequencia("introducao","cao") deve retornar \,7.
  • busca_sequencia("introducao","dao") deve retornar -1.
  • busca_sequencia("introducao","introducao") deve retornar \,0.
  • busca_sequencia("intro","introducao") deve retornar -1.
  • busca_sequencia("introducao","caoo") deve retornar -1.
Informações relevantes fornecidas:
  • receberemos duas strings arbitrárias;
  • comportamento quando não há correspondência: retornar -1;
  • comportamento quando seq é igual a texto: retornar índice \,0;
  • proibido usar in (não usar expressão como if seq in texto:).

Passo 2

Definindo claramente os casos especiais (edge cases) que precisamos tratar antes de implementar:
  1. Se seq for a string vazia ("") — comportamento típico de funções de busca é retornar o índice \,0 (a substring vazia “aparece” no início). Vamos adotar isso: se seq == "" retornamos \,0.
  2. Se o comprimento de seq for maior que o comprimento de texto — impossível de encontrar, retornamos -1.
  3. Caso geral: 0 < len(seq) <= len(texto) — precisamos procurar a primeira posição onde todos os caracteres de seq casem com uma fatia de texto.
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 percorre texto da esquerda para a direita.
  • Em cada posição possível i da janela, comparamos caractere a caractere se texto[i + j] == seq[j] para todo j de 0 até len(seq)-1.
  • Se todos os caracteres casarem, retornamos a posição i (primeira ocorrência).
  • Se chegarmos ao fim sem encontrar, retornamos -1.
Por que isso funciona? Porque qualquer ocorrência de seq em texto começa em alguma posição i entre 0 e 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) e m = 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 — se seq é maior que texto não cabe.
  • for i in range(n - m + 1): — percorre todas as posições iniciais possíveis. Note que range(n - m + 1) gera valores de 0 até n-m (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 i.
  • Se completarmos todos os j sem quebrar, significa que todos os caracteres casaram — retornamos i.
  • Se o laço externo terminar sem retorno, retornamos -1.
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 i (até n-m+1 posições) comparamos até m caracteres, então a complexidade é O(n \cdot m).
  • 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

Passo 7

Exemplos explicados passo a passo (mostrando como o algoritmo chega à resposta):
  1. busca_sequencia("introducao","cao"):
  • texto = "introducao", seq = "cao".
  • n = 10 (índices 0 a 9), m = 3.
  • i percorre de 0 até 10 - 3 = 7.
  • Para i = 7: comparamos
    • texto[7] com seq[0]'c' == 'c' ok;
    • texto[8] com seq[1]'a' == 'a' ok;
    • texto[9] com seq[2]'o' == 'o' ok.
  • Todos casaram, retornamos 7. Isso bate com o exemplo.
  1. busca_sequencia("introducao","dao"):
  • m = 3, i vai até 7.
  • Em todas as janelas de tamanho 3 nenhuma tem os três caracteres na ordem 'd','a','o'.
  • Logo retornamos -1.
  1. busca_sequencia("introducao","introducao"):
  • n = m = 10. range(n-m+1) é range(1) → só i = 0.
  • Compara todos os caracteres; todos casam; retorna 0.
  1. busca_sequencia("intro","introducao"):
  • m = 10, n = 5. Como m > n, retornamos -1 imediatamente.
  1. busca_sequencia("introducao","caoo"):
  • m = 4, n = 10. Nenhuma janela de 4 caracteres tem 'c','a','o','o' em sequência; retornamos -1.

Passo 8

Dicas para a prova (resumindo o que lembrar na hora):
  • Pense em janela deslizante: você só precisa testar posições iniciais 0 a n-m.
  • 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

Exercícios relacionados