0

C++ で大きな回文を見つけるプログラムを作成しています。大文字と小文字、句読点、および空白を無視して、入力された文字列の回文を取得する必要があります。たとえば、次の行を参照してください。

Confusius say: マダム、私はアダムです。

ここで、最大の回文はマダムです。大文字と小文字、句読点、空白を無視すると、私はアダムです。

また、プログラムは、2000 文字の文字列を 1 秒未満でテストできるように効率的でなければなりません。したがって、最大の回文を返すための次のコードがあります。

string largestPal(string input_str) {
    string isPal = "";
    string largest = "";

    int j, k;
    for(int i = 0; i < (input_str.length() - 1); ++i) {
        k = i + 1;
        j = i - 1;

        if(j >= 0 && k < (input_str.length())) {
            if(input_str[i] == input_str[j])
                j--;
            else if(input_str[i] == input_str[j])
                k++;
        }

        while(j >= 0 && k < (input_str.length())) {
            if(input_str[j] != input_str[k])
                break;

            else {
                j--;
                k++;
            }

            isPal = input_str.substr(j + 1, k - j - 1);
            if(isPal.length() > largest.length()) {
                largest = isPal;
            }
        }
    }
    return largest;
}

そして、このメソッドのパラメーターとして完全にフォーマットされた文字列 (空白、句読点、大文字と小文字を区別しない) を入力してみましたが、必要な出力を得ることができました。(たとえば、前の例では、最大の回文としてMADAMIMADAMが返されます。

質問：

この文字列を元の状態に戻すにはどうすればよいですか (句読点、空白、大文字と小文字を使用)。

また

メソッド内でストリップされた文字列を直接テストする方法はありますlargestPalが、選択した最大の回文に対応する元の文字列 (ストリップされていない) を返すにはどうすればよいですか?

どんな助けでも大歓迎です！

4

3 に答える 3

2

最も簡単な方法は、削除された文字列の文字を、削除されていない文字列の元の位置にマップするテーブルを作成することです。

たとえば、入力が「a V, v」の場合、削除された文字列は「avv」になります。マップは 1,3,6 になります。これは、ストリップされた文字列の最初の文字がストリップされていない最初の文字であり、次が 3 番目、次が 6 番目であることを示します。文字列を剥がしながら、このマップを作成します。

最終出力が得られたら、ストリップされた文字列でそれを見つけます。削除された文字列の最初と最後の文字の元の文字列のインデックスを検索し、その範囲の文字を出力します。

したがって、「avv」1,3,6 の場合、ストリップされた出力は「vv」になります。「avv」で「vv」を見つけ、対応するインデックスを検索して 3,6 を取得します。つまり、元の文字列に含まれる 3 ～ 6 文字を出力するか、「V, v」とします。

于 2012-04-26T08:22:58.887 に答える
2

次の 2 つの戦略があります。

  • スライスのシステムと特定のコンパレータを使用して、変更されていない文字列で遊ぶ
  • 正規バージョンを使用して回文を探しますが、それらがどこから来たのかを覚えておいてください

2 番目の戦略を選択した場合、あとは元の文字列のどこにいたかを思い出すだけです。回文の最初の文字のインデックスを覚えていれば、文字を数えるだけで元の文字列の回文を取得できます。

于 2012-04-26T08:34:26.300 に答える
0

回文を検索するときは、文字位置を保存する必要があります。したがって、戻り値は文字列ではなく、位置のペアでなければなりません。

次に、元の文字列を、文字列を取り除いたときと同様の方法で処理します。空白と句読点をスキップし、文字を数えて開始位置と終了位置を見つけます。

于 2012-04-26T08:24:09.627 に答える