Come determinare in modo efficiente il palindromo di un singolo carattere più lungo in una determinata stringa?

Question

Dato una stringa di lunghezza N contenente caratteri [A-Z], come faccio a determinare il palindromo più lungo per un singolo carattere?

Illustrerò con un esempio:

stringa data: JOHNOLSON Nell'analizzare la stringa, troviamo che abbiamo un palindromo con il carattere O in modo tale che la stringa assomiglia JOHNOLSON. Il palindromo per il 's O è di lunghezza 7 essenzialmente cercando come O--O--O. Inoltre, si noti che non v'è un palindromo con N, ma è solo di lunghezza 6.

Un altro esempio, stringa Dato: ABCJOHNOLSON dà lo stesso risultato di cui sopra con un palindromo dei O 's di lunghezza di 7 assomigliare O--O--O.

Tuttavia, con la stringa data ABCJOHNOLSONDA, il più lungo palindromo carattere individuale è di lunghezza 14 con il carattere A cercando come A------------A.

Altri esempi semplici comprendono:

ABA ->A-A (lunghezza 3)

ABAXYZ ->A-A (lunghezza 3)

ABAXYZA ->A---A (lunghezza 5), ​​non è la lunghezza 7 perché A-A---A non è un palindromo per la lettera A.

Prestare particolare attenzione all'ultimo esempio perché illustra una delle sottili sfumature del problema.

Answer 1

È possibile farlo in tempo lineare, è descritto here con un esempio di codice.

Answer 2

Ecco cosa mi è venuto in mente, non so quanto possa essere efficiente.

 
For every letter in the alphabet, 
    Find the first and last occurrence of this letter. 
    While the substring is not a palindrome for that letter (easy to check), 
    find the next letter on both sides so that every possible combination is 
    checked. Take the longest one and store it. 
Take the longest one. 

Answer 3

Definitivamente non ottimale. Assume che la stringa di input sia tutto in minuscolo.

using System; 
using System.Collections.Generic; 

public class LongestPalindrome 
{ 
    public int longest(string s) 
    { 
     Dictionary<char, List<int>> indices = 
      new Dictionary<char, List<int>>(); 

     // find all indices for each letter 
     for (int i = 0; i < s.Length; i++) 
     { 
      char c = s[i]; 
      if (!indices.ContainsKey(c)) 
        indices.Add(c, new List<int>()); 
      indices[c].Add(i); 
     } 

     int max = Int32.MinValue; 

     for (int i = (int)'a'; i <= (int)'z'; i++) 
     { 
      char c = (char)i; 

      // in case a letter didn't appear at all in the input string 
      if (!indices.ContainsKey(c)) continue; 

      List<int> indexList = indices[c]; 

      // in case a letter appeared only once in the input string 
      if (indexList.Count == 1) max = Math.Max(max, 1); 

      for (int j = 0; j < indexList.Count; j++) 
      { 
       for (int k = j + 1; k < indexList.Count; k++) 
       { 
        int dist = indexList[k] - indexList[j] + 1; 
        string sub = s.Substring(indexList[j], dist); 
        if (isPalendrome(sub, c)) 
             max = Math.Max(max, dist); 
       } 
      } 
     } 

     return max; 
    } 

    bool isPalendrome(string s, char c) 
    { 
     int i = 0; 
     while(i < s.Length - 1 - i) 
     { 
      if (s[i] != c && s[s.Length - 1 - i] != c) 
      { 
       i++; 
       continue; 
      } 
      if (s[i] != s[s.Length - 1 - i]) return false; 
      i++; 
     } 
     return true; 
    } 
}