8

質問：

任意の文字列が与えられた場合、可能な限り最小限の文字数を追加して、線形時間で回文にします。

O(N 2 ) の解しか思いつきません。

誰かが O(N) ソリューションを手伝ってくれますか?

4

11 に答える 11

2

@Chronicalの答えは間違っていると思います.big -Oの複雑さを計算するために使用される最悪のケースではなく、最良のケースのシナリオのようです。私は証明を歓迎しますが、「解決策」は実際には有効な答えを説明していません。

KMP は、一致する部分文字列 ( は入力文字列の長さ) と検索対象の部分文字列を時間内に見つけますが、入力文字列内の最長の回文が何であるかをO(n * 2k)時間内に教えてくれません。nkO(n)

この問題を解決するには、文字列の最後にある最も長い回文を見つける必要があります。この最長の接尾辞回文の長さがxである場合、追加する文字の最小数は ですn - x。たとえば、文字列aabaの最長のサフィックス部分文字列abaの長さ3は であるため、答えは1です。文字列が回文かどうかを調べるアルゴリズムは、O(n)KMP を使用するか、より効率的で単純なアルゴリズムを使用するかに関係なく、時間がかかります ( O(n/2))。

最初の文字と最後の文字に 1 つずつ、合計 2 つのポインターを取得します。

ポインターの位置の文字を比較し、等しい場合は各ポインターを内側に移動し、そうでない場合は戻りますfalse

ポインターが同じインデックス (文字列の長さが奇数) を指している場合、または重複している (文字列の長さが偶数) 場合は、戻ります。true

単純なアルゴリズムを使用して、文字列全体から開始し、それが回文であるかどうかを確認します。そうである場合は を返し0、そうでない場合は文字列をチェックし、 1 文字string[1...end]にstring[2...end]なるまで を返しn - 1ます。これにより、実行時間がO(n^2).

KMP アルゴリズムの分割

ビルドテーブル

最長のサフィックス回文を検索する

テーブルの構築にはO(n)時間がかかり、各部分文字列の「あなたは回文ですか」の各チェックには時間string[0...end], string[1...end], ..., string[end - 2...end]がかかりO(n)ます。kこの場合、nは単純なアルゴリズムが各部分文字列をチェックするのに必要な係数と同じです。これは、単純なアルゴリズムが行ったのとまったく同じように、として開始しk = n、次に を通過するk = n - 1ためです。k = n - 2

TL; 博士:

KMP は、文字列が回文であるかどうかを時間的に判断できますが、すべての部分文字列が回文であるかどうかを確認する必要があり、単純な回文チェック アルゴリズムと同じ (ただし実際にはより悪い) 実行時間になるO(n)ため、質問に対する答えが得られます。 string[0...end], string[1...end], ..., string[end - 2...end].

于 2016-08-08T14:36:58.470 に答える
1

O(n) 時間のソリューション。アルゴリズム: 指定された文字列内で最後の文字を含む最長の回文を見つける必要があります。次に、回文の一部ではないすべての文字を文字列の後ろに逆の順序で追加します。

重要なポイント: この問題では、指定された文字列の最長の回文には最後の文字が含まれている必要があります。

例: 入力: abacac 出力: abacacaba ここで、最後の文字を含む入力の中で最も長い回文は "cac" です。したがって、「cac」の前のすべての文字を逆の順序で後ろに追加して、文字列全体を回文にします。

C# で記述され、いくつかのテスト ケースがコメント化されている

 static public void makePalindrome()
    {
        //string word = "aababaa";
        //string word = "abacbaa";
        //string word = "abcbd";
        //string word = "abacac";
        //string word = "aBxyxBxBxyxB";
        //string word = "Malayal";
        string word = "abccadac";

        int j = word.Length - 1;
        int mark = j;
        bool found = false;

        for (int i = 0; i < j; i++)
        {
            char cI = word[i];
            char cJ = word[j];

            if (cI == cJ)
            {
                found = true;
                j--;
                if(mark > i)
                    mark = i;
            }
            else
            {
                if (found)
                {
                    found = false;
                    i--;
                }
                j = word.Length - 1;
                mark = j;
            }
        }

        for (int i = mark-1; i >=0; i--)
            word += word[i];

        Console.Write(word);

    }
}

このコードは、文字列を回文にするために APPEND TO THE BACK の最小量の文字の解決策を提供することに注意してください。前に追加したい場合は、逆の2番目のループを用意してください。これにより、アルゴリズムは O(n) + O(n) = O(n) になります。文字列の任意の場所に文字を挿入して回文にする方法が必要な場合、このコードはその場合には機能しません。

于 2015-02-20T20:57:51.210 に答える
1 
#include<iostream>
#include<string>

using std::cout;
using std::endl;
using std::cin;

int main() {

    std::string word, left("");
    cin >> word;
    size_t start, end;

    for (start = 0, end = word.length()-1; start < end; end--) {
        if (word[start] != word[end]) { 
            left.append(word.begin()+end, 1 + word.begin()+end);
            continue;
        }
        left.append(word.begin()+start, 1 + word.begin()+start), start++;
    }
    cout << left << ( start == end ? std::string(word.begin()+end, 1 + word.begin()+end) : "" ) 
        << std::string(left.rbegin(), left.rend()) << endl;
    return 0;
}

最小数を追加するかどうかはわかりませんが、回文が生成されます

説明:

  • 指定された文字列の両端から開始し、中央に向かって内側に繰り返します。

  • 各反復で、各文字が同じかどうか、つまりword[start]== word[end]? をチェックします。

    • それらが同じ場合、変数のコピーword[start]を別の文字列と呼ばれる名前に追加しますleft。これは、名前が示すように、反復が完了したときに新しい回文文字列の左側として機能します。次に、両方の変数 ( start)++ と ( end)-- を中央に向かってインクリメントします。
    • それらが同じでない場合、変数のコピーをword[end]同じ文字列に追加しますleft

  • そして、これがループが完了するまでのアルゴリズムの基本です。

  • ループが終了すると、奇数の長さの回文を取得した場合は、形成された新しい回文の中央に中央の文字を追加することを確認するために、最後のチェックが行われます。

反対の文字を string に追加するleftと、コード内のすべてについて反対のことが真になることに注意してください。つまり、各反復でどのインデックスが増分され、一致が見つかったときにどのインデックスが増分されるか、回文を印刷する順序などです。もう一度やり直す必要はありませんが、試してみてください。

クラスの追加メソッドが一定時間で実行されると仮定すると、このコードの実行の複雑さはO(N)になるはずです。std::string

于 2013-09-11T05:47:02.570 に答える
0

既存の文字を置き換えたり削除したりできないと思いますか?

まず、文字列の 1 つを反転し、反転した文字列と他の文字列の間の最長共通部分文字列 (LCS) を見つけます。これは宿題や面接の質問のように聞こえるので、あとはあなたに任せます。

于 2013-09-11T04:33:08.657 に答える
0

ここでこの解決策を参照してください これは O(N^2) よりも優れています
問題は他の多くのサブ問題に分割されます
例:
元の「tostotor」
が逆の「rototsot」
ここで 2 番目の位置は「o」なので、割り込むことで 2 つの問題に分割されます元の文字列から "t" と "ostot" へ
't' の場合:解は 1
'ostot' の場合:解は 2です。なぜなら、LCS は "tot"であり、追加する必要がある文字は"os"
であるため、合計は2+1です= 3

def  shortPalin( S):
    k=0
    lis=len(S)
        for i in range(len(S)/2):
        if S[i]==S[lis-1-i]:
            k=k+1
        else :break
    S=S[k:lis-k]
    lis=len(S)
    prev=0
    w=len(S)
    tot=0
    for i in range(len(S)):
        if i>=w:
            break;
        elif S[i]==S[lis-1-i]:
             tot=tot+lcs(S[prev:i])
             prev=i
             w=lis-1-i
    tot=tot+lcs(S[prev:i])
    return tot

def  lcs( S):
    if (len(S)==1):
        return 1
    li=len(S)
    X=[0 for x in xrange(len(S)+1)]
    Y=[0 for l in xrange(len(S)+1)]
    for i in range(len(S)-1,-1,-1):
        for j in range(len(S)-1,-1,-1):
            if S[i]==S[li-1-j]:
                X[j]=1+Y[j+1]
            else:
                X[j]=max(Y[j],X[j+1])
        Y=X
    return li-X[0]
print shortPalin("tostotor")
于 2014-07-29T00:14:55.943 に答える