文字列で最も長い回文を見つけようとしていました。力ずくで解決するには O(n^3) 時間かかります。サフィックスツリーを使用した線形時間アルゴリズムがあることを読みました。私は接尾辞ツリーに精通しており、それらを快適に構築できます。構築されたサフィックス ツリーを使用して最長の回文を見つけるにはどうすればよいですか。
質問する
27367 次
5 に答える
31
線形解はこの方法で見つけることができます::
前提条件:
(1)。O(N) または O(NlogN) 時間でサフィックス配列を構築する方法を知っている必要があります。
(2)。標準の LCP 配列を見つける方法を知っている必要があります。隣接するサフィックス i と i-1 の間の LCP
すなわち。LCP [i]=LCP (ソート済み配列の接尾辞 i、ソート済み配列の接尾辞 i-1) for (i>0)。
Sを元の文字列、S 'を元の文字列の逆とする。S="バナナ"を例に取りましょう。次に、逆文字列 S'=ananab です。
ステップ 1 : S + # + S'を連結して文字列 Str を取得します。ここで、 # は元の文字列に存在しないアルファベットです。
Concatenated String Str=S+#+S'
Str="banana#ananab"
ステップ 2:文字列 Str の Suffix Array を作成します。
この例では、サフィックス配列は次のとおりです。
Suffix Number Index Sorted Suffix
0 6 #ananab
1 5 a#ananab
2 11 ab
3 3 ana#ananab
4 9 anab
5 1 anana#ananab
6 7 ananab
7 12 b
8 0 banana#ananab
9 4 na#ananab
10 10 nab
11 2 nana#ananab
12 8 nanab
サフィックス配列は、辞書順で文字列のサフィックスの開始位置を与える整数の配列であることに注意してください。したがって、開始位置のインデックスを保持する配列はサフィックス配列です。
つまり、SuffixArray[]={6,5,11,3,9,1,7,12,0,4,10,2,8};
ステップ 3 : 接尾辞配列を作成できたので、隣接する接尾辞の間の最も長い共通の接頭辞を見つけます。
LCP between #ananab a#ananab is :=0
LCP between a#ananab ab is :=1
LCP between ab ana#ananab is :=1
LCP between ana#ananab anab is :=3
LCP between anab anana#ananab is :=3
LCP between anana#ananab ananab is :=5
LCP between ananab b is :=0
LCP between b banana#ananab is :=1
LCP between banana#ananab na#ananab is :=0
LCP between na#ananab nab is :=2
LCP between nab nana#ananab is :=2
LCP between nana#ananab nanab is :=4
したがって、LCP 配列LCP={0,0,1,1,3,3,5,0,1,0,2,2,4} となります。
ここで、LCP[i] = サフィックス i とサフィックス (i-1) の間の最長共通プレフィックスの長さ。(i>0 の場合)
ステップ 4:
これで、LCP アレイが構築されました。次のロジックを使用します。
Let the length of the Longest Palindrome ,longestlength:=0 (Initially)
Let Position:=0.
for(int i=1;i<Len;++i)
{
//Note that Len=Length of Original String +"#"+ Reverse String
if((LCP[i]>longestlength))
{
//Note Actual Len=Length of original Input string .
if((suffixArray[i-1]<actuallen && suffixArray[i]>actuallen)||(suffixArray[i]<actuallen && suffixArray[i-1]>actuallen))
{
//print :Calculating Longest Prefixes b/w suffixArray[i-1] AND suffixArray[i]
longestlength=LCP[i];
//print The Longest Prefix b/w them is ..
//print The Length is :longestlength:=LCP[i];
Position=suffixArray[i];
}
}
}
So the length of Longest Palindrome :=longestlength;
and the longest palindrome is:=Str[position,position+longestlength-1];
実行例 ::
actuallen=Length of banana:=6
Len=Length of "banana#ananab" :=13.
Calculating Longest Prefixes b/w a#ananab AND ab
The Longest Prefix b/w them is :a
The Length is :longestlength:= 1
Position:= 11
Calculating Longest Prefixes b/w ana#ananab AND anab
The Longest Prefix b/w them is :ana
The Length is :longestlength:= 3
Position:=9
Calculating Longest Prefixes b/w anana#ananab AND ananab
The Longest Prefix b/w them is :anana
The Length is :longestlength:= 5
Position:= 7
So Answer =5.
And the Longest Palindrome is :=Str[7,7+5-1]=anana
メモしてください::
ステップ 4 の if 条件は、基本的に、各反復 (i) で、接尾辞 s1(i) および s2(i-1) を使用する場合、"s1 には # が含まれている必要があり、s2 には # " OR "s2 が含まれていてはならないs1 には # が含まれている必要があり、s1 には # " が含まれていてはなりません。
|(1:BANANA#ANANAB)|leaf
tree:|
| | | |(7:#ANANAB)|leaf
| | |(5:NA)|
| | | |(13:B)|leaf
| |(3:NA)|
| | |(7:#ANANAB)|leaf
| | |
| | |(13:B)|leaf
|(2:A)|
| |(7:#ANANAB)|leaf
| |
| |(13:B)|leaf
|
| | |(7:#ANANAB)|leaf
| |(5:NA)|
| | |(13:B)|leaf
|(3:NA)|
| |(7:#ANANAB)|leaf
| |
| |(13:B)|leaf
|
|(7:#ANANAB)|leaf
于 2012-06-29T09:07:21.460 に答える
25
このように進める必要があると思います：
y 1 y 2 ... y nを文字列とします ( y iは文字です)。
S f = y 1 y 2 ... y n $およびS r = y n y n - 1 ... y 1 #の一般化されたサフィックス ツリーを作成します(文字を逆にして、 S f ($)の異なる末尾文字を選択します)。およびS r (#))... ここで、S fは"String, Forward"を表し、 S rは"String, Reverse"を表します。
S fのすべての接尾辞iについて、S rの接尾辞n - i + 1を持つ最も低い共通の祖先を見つけます。
ルートからこの最低共通祖先まで続くのは回文です。これは、最低共通祖先がこれら 2 つの接尾辞の最長の共通接頭辞を表すためです。それを思い出します：
(1) 接尾辞の接頭辞は部分文字列です。
(2)回文とは、その裏返しと同じ文字列です。
(3) したがって、文字列内に含まれる最長の回文は、まさにこの文字列の最長の共通部分文字列であり、その逆です。
(4) したがって、文字列内に含まれる最長の回文は、文字列とその逆の間の接尾辞のすべてのペアの中で最も長い共通の接頭辞です。これが私たちがここで行っていることです。
例
バナナという単語を見てみましょう。
S f = バナナ $
S r = アナナブ#
以下は、 S fとS rの一般化されたサフィックス ツリーです。ここで、各パスの末尾の数字は、対応するサフィックスのインデックスです。小さな間違いがあります。Blue_4 の親の 3 つのブランチすべてに共通するaは、 nの横の入力エッジにある必要があります。
ツリーの最下位の内部ノードは、この文字列の最長の共通部分文字列であり、その逆です。したがって、ツリーのすべての内部ノードを見ると、最も長い回文が見つかります。
最も長い回文は、Green_0 と Blue_1 の間 (つまり、bananaとanana )の間にあり、 ananaです。
編集
この質問に答えるこの論文を見つけました。
于 2011-08-12T18:30:27.763 に答える
7
数年遅れ…
sが元の文字列であるとr仮定し、s逆にします。STまた、 を使用してサフィックス ツリーを完全に構築したと仮定しましょうs。
次のステップは、ragainstのすべての接尾辞をチェックすることSTです。の新しいサフィックスごとに、ツリー内の既存のサフィックス (つまり、 のサフィックスの 1 つ) に対して正常に一致しrた最初の文字の数を維持します。ks
例として、 の接尾辞"RAT"に一致し、 "RA"で始まるいくつかの接尾辞が含まれているrとしますが、 "RAT"に一致するものはありません。最後の文字"T"への希望を最終的に放棄しなければならなかったとき、 は 2 になります。のサフィックスの最初の 2 文字と のサフィックスの最初の 2 文字を一致させました。到達したこのノードを と呼びます。skrsn
では、回文を見つけたときはどうすればわかりますか? の下にあるすべてのリーフ ノードをチェックしnます。
従来のサフィックス ツリーでは、各サフィックスの開始インデックスは、そのサフィックス ブランチのリーフ ノードに格納されます。上記の例では、 には"RA"sで始まる一連のサフィックスが含まれている可能性があり、それぞれのサフィックスは のリーフ ノードの子孫に存在するインデックスの 1 つで始まります。n
これらの指標を使用してみましょう。
の部分文字列の文字を の文字とk照合すると、どういう意味になるでしょうか? これは単純に、一部の文字列が逆になっていることを発見したことを意味します。しかし、部分文字列の開始位置がplusの一致する部分文字列と等しい場合、それはどういう意味でしょうか? はい、それは!と同じように読むことを意味します。したがって、サイズ の回文を見つけた定義になります。 RkSTRSks[i] through s[i+k]s[i+k] through s[i]k
あとは、これまでに見つかった最長の回文にタブを付けておき、関数の最後でそれを返すだけです。
于 2015-01-08T03:46:04.357 に答える
2
からの簡単で短い説明Skiena - The Algorithm Design Manual
S で最も長い回文を見つける [サフィックス ツリーを使用] –回文とは、 madamのように文字の順序を逆にしても同じように読み取れる文字列です。文字列 S で最長の回文を見つけるには、S のすべてのサフィックスと S の反転を含む単一のサフィックス ツリーを構築します。各リーフはその開始位置によって識別されます。回文は、同じ位置から順方向および逆方向の子を持つこのツリー内の任意のノードによって定義されます。
于 2014-11-01T12:31:16.993 に答える
-2
DP ソリューション:
int longestPalin(char *str)
{
n = strlen(str);
bool table[n][n]l
memset(table, 0, sizeof(table));
int start = 0;
for(int i=0; i<n; ++i)
table[i][i] = true;
int maxlen = 1;
for(int i=0; i<n-1; ++i)
{
if(str[i] == str[i+1])
{
table[i][i] = true;
start = i;
maxlen = 2;
}
}
for(int k=3; k<=n; ++k)
{
for(int i=0; i<n-k+1; ++i)
{
int j = n+k-1;
if(str[i] == str[j] && table[i+1][j-1])
{
table[i][j] = true;
if(k > maxlen)
{
start = i;
maxlen = k;
}
}
}
}
print(str, start, start+maxlen-1);
return maxlen;
}
于 2014-01-06T19:11:55.753 に答える