Longest Palindromic Substring

Una sottostringa è definita dal suo primo indice i e dal suo ultimo indice j. Verificala con due puntatori: confronta s[i] con s[j], poi s[i+1] con s[j-1], e così via, fermandoti alla prima differenza. Se i puntatori si incontrano o si incrociano senza trovare differenze, la sottostringa è un palindromo. Conserva la più lunga che trovi.

Per la regola in caso di parità, procedi con gli indici iniziali da sinistra a destra e sostituisci la migliore solo quando un nuovo palindromo è strettamente più lungo. Un palindromo successivo della stessa lunghezza non sostituirà mai uno precedente, quindi restituirai quello più a sinistra.

Questo esamina tutte le n(n+1)/2 sottostringhe, quindi non può non trovare la risposta. È lento perché ogni verifica può scorrere metà della sottostringa. Per una stringa di 2000 copie di a, ogni sottostringa è un palindromo e ogni verifica arriva fino al centro: circa n³/12 ≈ 6.7 × 10^8 confronti tra lettere.

La forza bruta dimentica ciò che ha imparato. Quando esamina "anana", confronta a con a e poi n con n: il secondo confronto è l'intero test di "nan", che ha già eseguito. La regola che evita questo lavoro: s[i..j] è un palindromo quando i suoi due estremi coincidono e la parte compresa tra loro, s[i+1..j-1], è un palindromo. Un confronto e una risposta memorizzata bastano per determinare ogni sottostringa.

Memorizza le risposte in una tabella pal[i][j] e riempila in base alla lunghezza. Ogni singola lettera è un palindromo. Una sottostringa di due lettere lo è quando le due lettere coincidono. Per le lunghezze maggiori, applica la regola: la parte interna è più corta di due lettere, quindi la sua cella è già stata riempita.

In "bananas", pal[1][5] ("anana") è vero perché s[1] e s[5] sono entrambe a, e pal[2][4] ("nan") è vero. Le lunghezze aumentano e gli indici iniziali procedono da sinistra a destra, quindi il primo palindromo di una nuova lunghezza record è anche quello più a sinistra di quella lunghezza. Circa n²/2 celle richiedono O(1) ciascuna, quindi il tempo è O(n²); il costo è la memoria: 4 × 10^6 celle per n = 2000.

Ogni palindromo ha un centro. Uno di lunghezza dispari, come "anana", è centrato su una lettera; uno di lunghezza pari, come "abba", è centrato sullo spazio tra le due lettere centrali. Una stringa di lunghezza n ha n lettere e n-1 spazi, quindi 2n-1 centri possibili.

Partendo da un centro, procedi verso l'esterno di una lettera per lato finché le due lettere coincidono. Ogni passo dimostra l'esistenza di un palindromo più lungo di due lettere. La prima discordanza, oppure il bordo della stringa, interrompe l'esplorazione: nessun palindromo più lungo può avere lo stesso centro, perché includerebbe la coppia di lettere discordanti. Quindi, un'unica esplorazione verso l'esterno trova il palindromo più lungo attorno a ciascun centro, e il più lungo tra questi è la risposta.

In "bananas", parti dalla lettera a all'indice 3. Le lettere agli indici 2 e 4 sono entrambe n, quelle agli indici 1 e 5 sono entrambe a, e quelle agli indici 0 e 6 sono b e s, quindi l'esplorazione si ferma con lunghezza 5. L'inizio è 3 - (5-1)/2 = 1, che dà "anana". La stessa formula, center - (length-1)/2 arrotondata per difetto, funziona anche per i centri negli spazi.

Esplora i centri da sinistra a destra e sostituisci il migliore solo quando trovi una lunghezza strettamente maggiore. Due palindromi della stessa lunghezza hanno la stessa parità e quello con il centro più a sinistra inizia prima, quindi vince quello più a sinistra. Il caso peggiore è una stringa composta da una sola lettera ripetuta: da ciascun centro si procede fino al bordo più vicino, per circa n²/2 = 2 × 10^6 passi quando n = 2000; la memoria richiesta è di pochi interi.