8

文字[AZ]を含む長さNの文字列がある場合、個々の文字の最長の回文を決定するにはどうすればよいですか？

これを例で説明します。

与えられた文字列：文字列を分析すると、文字列がのように見えるJOHNOLSON 文字を持つ回文があることがわかります。'sの回文は、長さが7で、基本的にはのように見えます。また、が付いた回文がありますが、長さは6だけであることに注意してください。OJOHNOLSONOO--O--ON

別の例、与えられABCJOHNOLSONた文字列：上記と同じ結果が得られます。O長さ7の回文はのように見えます。O--O--O

ただし、指定された文字列ABCJOHNOLSONDAでは、最長の個々の文字の回文は長さが14で、文字はのようにA見えます。A------------A

その他の簡単な例は次のとおりです。

ABA-> （長さ3）A-A

ABAXYZ-> （長さ3）A-A

ABAXYZA-> （長さ5）、文字の回文ではないため、長さ7ではありません。A---AA-A---AA

最後の例は問題の微妙なニュアンスの1つを示しているため、特に注意してください。

4

3 に答える 3

5

線形時間でそれを行うことができます。ここではコードサンプルを使用して説明します。

于 2011-11-20T19:02:04.103 に答える
0

これが私が思いついたものです、私はそれがどれほど効率的であるかわかりません。

アルファベットのすべての文字について、
    この手紙の最初と最後の出現を見つけてください。
    部分文字列はその文字の回文ではありませんが（確認が簡単です）、
    可能なすべての組み合わせが次のようになるように、両側で次の文字を見つけます
    チェックしました。最も長いものを取り、それを保管してください。
一番長いものを取りなさい。
于 2011-11-20T19:02:57.850 に答える
0

間違いなく最適ではありません。入力文字列はすべて小文字であると想定しています。

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;
    }
}
于 2011-11-20T20:41:01.093 に答える