Finding a Motif in DNA

String Algorithms

Descrizione

Data una stringa t, essa è una sottostringa di s se è contenuta come sequenza contigua di simboli in s. Il problema chiede di trovare tutte le posizioni (locations) in cui t compare come sottostringa di s, usando l'indicizzazione 1-based (a differenza di Python, che usa 0-based).

Given

Due stringhe di DNA s e t (ciascuna di lunghezza massima 1 kbp).

Return

Tutte le posizioni (1-based) in cui t compare come sottostringa di s.

Sample Dataset

GATATATGCATATACTT
ATAT

Sample Output

2 4 10

La mia esecuzione

08/24/2026 11:24:47

Input · dataset.txt

CCTCTTAAATCTTAAAGGTCTTAAACATTCTTAAATAGTGTGGTTCGAGTCTTAAATCTTAAAGGATGCTCTTAAATCTTAAATTCTTAAAGGTCTTAAAGATCTTAAACGTTTTCTTAAATTATCTTAAACATTCTTAAAACGGCTCTTAAATCTTAAATCAATCTTAAAAAGTCTTAAAATCTTAAATGATATATCATTCTTAAATTTCTCTTAAAATTCTTAAATCGTTATAACTAAATAAGTCTTAAACCTCTTAAATCTTAAATTTATTATAACACTCTTAAAAGTATCTCTTAAAGATCTAGAGTCTTAAAACCTCTTAAAAGTCTTAAATCTTAAAAACGAAGTCTTAAATCTTAAAGTCTTAAAATCTTAAAGCCATCTTAAATTCTTGTTCGTCTTAAAGTGTGGAATCTTAAATCTTAAAGGTCTTAAATCTTAAATCTTAAACCGAAATCTTAAATCTTAAAGTCTTAAAACTCTTAAATACTCTTAAACTCTTAAAGTCTTAAACCGCTCTTAAAGTCTTAAACAGTCTTAAACTTCTTAAAATAAAGGTCCTCTCTGCGAGCTATTCTTAAAGCTTCAGGGAACATCTTAAAGTCTTAAACCATCTTAAACAAGATTCGGCAACTCTTAAATCTTAAAGGATCTCTTAAAACTCTTAAAACAGCGGGTCTTAAATCTCTTAAACTGAGTCTTAAACTCTTAAAATCAGAGGTCTTAAACCTCTTAAATCTTAAACTTTCCCGCTTAAAGTCTTAAATCTTAAACTCTTAAACGTCTTAAATCTTAAACCGATCTTAAAGCGAACATGAGGTCTTAAATCTTAAATCTTAAAATCTTAAACTCTTAAAGTCTTAAAATCTTAAACACTCTTAAATCTTAAATCTTAAATCTTAAAGCGGAATCTTAAACTAGGGTTCTTAAAACGCGTTCTTAAAAAAGTCTTAAACCTTGGGTCTCGTTGCATCTTAAAGGCAAAGTCTTAAA
TCTTAAATC

Output · run_log.txt

3 50 70 147 154 221 255 330 351 417 433 440 460 638 681 734 763 787 824 831 880 887 894

Esegui nel browser · Pyodide

Mostra il codice sorgente (problem.py)

filename = "dataset.txt"
with open(filename) as f:
    s = f.readline().rstrip("\n")
    t = f.readline().rstrip("\n")

match = lambda x: s[x:x+len(t)] == t

result = [str(i+1) for i in range(len(s)) if match(i)]
print(" ".join(result))

Soluzione JavaScript

Esegui ora, live

Mostra il codice sorgente

// Finding a Motif in DNA (Rosalind ID: SUBS) - soluzione JavaScript
// indipendente, non una trascrizione di problem.py: stessa logica
// (tutte le posizioni 1-indexed dove t compare in s, sovrapposizioni
// incluse), riscritta in modo idiomatico per JS.
//
// Contratto: riceve il contenuto testuale di dataset.txt, restituisce
// l'output testuale (stessa forma dell'output Python).
export default function solve(datasetText) {
  const [s, t] = datasetText.split("\n").map((riga) => riga.trim());

  if (!s || !t) {
    throw new Error(`Input non valido: attese due righe non vuote, ricevuto "${datasetText.trim()}"`);
  }

  const result = [];
  for (let i = 0; i <= s.length - t.length; i++) {
    if (s.slice(i, i + t.length) === t) {
      result.push(i + 1);
    }
  }

  return `${result.join(" ")}\n`;
}