5

最大 20,000 文字の文字列で最大の回文を見つけるよう求める問題を解決しようとしています。すべての部分文字列が回文であるかどうかを確認しようとしましたが、うまくいきましたが、明らかに遅すぎました。少しグーグルした後、私はこの素晴らしいアルゴリズム http://stevekrenzel.com/articles/longest-palnidromeを見つけました。私はそれを実装しようとしましたが、動作させることができません。また、指定された文字列には不正な文字が含まれているため、それを有効な文字のみに変換し、すべての文字で最も長い回文を出力する必要があります。

これが私の試みです：

int len = original.length();
int longest = 0;
string answer;

for (int i = 0; i < len-1; i++){

    int lower(0), upper(0);

    if (len % 2 == 0){
        lower = i;
        upper = i+1;
    } else {
        lower = i;
        upper = i;
    }

    while (lower >= 0 && upper <= len){
        string s2 = original.substr(lower,upper-lower+1);
        string s = convert(s2);

        if (s[0] == s[s.length()-1]){
            lower -= 1;
            upper += 1;
        } else {
            if (s.length() > longest){
                longest = s.length();
                answer = s2;
            }
            break;
        }


    }
}

私はそれを機能させることができません.紙の上でこの正確なアルゴリズムを使用しようとしましたが、うまくいきました.助けてください. 必要な場合の完全なコードは次のとおりです。http://pastebin.com/sSskr3GY

編集：

int longest = 0;
string answer;
string converted = convert(original);
int len = converted.length();

if (len % 2 == 0){
    for (int i = 0; i < len - 1; i++){
        int lower(i),upper(i+1);
        while (lower >= 0 && upper <= len && converted[lower] == converted[upper]){
            lower -= 1;
            upper += 1;
        }
        string s = converted.substr(lower+1,upper-lower-1);
        if (s.length() > longest){
            longest = s.length();
            answer = s;
        }
    }
} else {
    for (int i = 0; i < len; i++){
        int lower(i), upper(i);
        while (lower >= 0 && upper <= len && converted[lower] == converted[upper]){
            lower -= 1;
            upper += 1;
        }
        string s = converted.substr(lower+1,upper-lower-1);
        if (s.length() > longest){
            longest = s.length();
            answer = s;
        }
    }
}

わかりましたので、問題を修正しました。完全に正常に動作しますが、変換された文字列の長さが奇数の場合のみです。助けてください。

4

3 に答える 3

3

2 つの主要なエラーが表示されます。

  1. 上位/下位ポインターを i,i または i,i+1 に初期化するかどうかは、元の文字列ではなく、検索する回文の長さのパリティに依存します。そのため (これ以上の最適化を行わない場合)、i が 0 から len (len-1) に移動する 2 つの別個のループが必要になります。
  2. アルゴリズムは、変換された文字列に対してのみ実行する必要があります。機能させるには、最初に元の文字列を変換する必要があります。

この文字列を考えてみましょう: abc^ba(where^は不正な文字です)、不正な文字を除いた最長の回文は明らかabcbaに ですが、 に到達しi==2、下限/上限を 1 つ移動すると、bc^部分文字列が定義され、変換後に になりますbc。b != cしたがって、この回文は拡張できないことを認めます。

于 2011-03-14T21:01:14.427 に答える