next配列の解
親文字列でサブ文字列を検索するには、多くの方法があります.KMPは最も一般的な改良アルゴリズムであり、マッチング中に不整合になった場合、効果的にいくつかの文字を後ろにジャンプし、マッチング速度を速めることができる.もちろん,このアルゴリズムはサブストリングに対称属性があり,対称属性があれば,再マッチング可能なコンテンツがあるかどうかを前方に検索する必要があることが分かる.
KMPアルゴリズムには、接頭辞配列と呼ばれる配列もあれば、next配列と呼ばれる配列もあり、各サブ列には固定的なnext配列があり、文字列マッチング中に不整合になった場合に数文字前にジャンプできることを記録しています.もちろん、サブ列の対称度も記述されています.程度が高いほど、値が大きくなります.もちろん、前に再マッチングの機会が現れる可能性があります.このnext配列の求め方はKMPアルゴリズムの鍵ですが、よく理解できません.私はここで通俗的な言葉で説明します.他のところに数学の公式が導き出しているのを見て、卵が痛くて、この文章は数学の公式を見るのが好きではなく、KMPアルゴリズムを理解したい学生にしか貢献していません.
1、一例で説明すると、以下はサブストリングのnext配列の値であり、このサブストリングの対称度が高いことがわかるので、next値はいずれも大きい.
位置i:>0 1 2 3 4 5 6 7 9 10 11 12 13 14 15接頭辞next[i]:>0 0 0 0 1 2 3 1 3 4 5 6 7 4 0サブ列:>a g c t a g c a g c t a g c t g c t g
次の対称は中心対称ではなく、abccbaではなくabcabcのような中心文字ブロック対称であることを明らかにします.(1)対称列を1つずつ検索する.
これは簡単です.私たちはこのサブストリングをループして、前の1文字、前の2文字、3つ...i個から最後の15個まで見ます.1つ目のaは対称性がないので、対称度0の前の2つのagは対称性がないので、0の順に前の0-4を類推しても同じように0の前の5つのagctaで、この列に1つのaが等しいことが見えます.だから、対称度は1の前の6つのagctagで、agとagの対成が見えます.対称度は2です.ここで注意します.そう思うと、プログラミングはどうやって実現しますか.a、前の文字の前の文字の対称度が0の場合、現在の文字とサブ列の最初の文字を比較する限り、次のルールに従います.これはよく理解して、前はすべて0で、説明はすべて非対称で、もし1つの文字をプラスしたら、対称にするならば最大で現在のと最初の対称です.例えばagctaという中のtは0で、後ろのaの対称度は最初の文字aに等しいかどうかを見るだけです.
b、この推理によって、私たちは1つの法則をまとめることができて、前が0であるだけではなくて、もし前の1つの文字のnext値が1であれば、私たちは現在の文字と子列の2番目の文字を比較して、前が1であるため、前の文字がすでに1番目の文字と等しくなったことを説明して、もしこれがまた2番目の文字と等しくなったら、対称の程度が2であることを説明します.2文字が対称になった.例えば上のagctag、最後から2番目のaのnextは1で、それが1番目のaと対称であることを説明して、それから私たちは最後のgを2番目のgと比較して、また等しくて、自然対称成都は累積して、2です.
c、上の推理に従って、ずっと等しければ、ずっと积み重ねて、ずっと押してもいいですよ.ここまで押すのは少しも难しいでしょう.もし难しいと思ったら、私が书いたのが失败したことを意味します.もちろんそんなにうまく対称になるわけではありません.次が等しくないと、前の対称性を継承できないことを説明します.このような状況はそんなに対称性がないことを説明するしかありませんが、対称性がないとは説明できません.だから、このような状況に遭遇したら、もう一度考えなければなりません.これも難点です.
(2)対称性を振り返る
ここではもう前を継承することはできませんが、対称成都を探していますか.最も愚かな方法はサブ関数を書くことはできません.この文字列の最大対称度を探して、どのように書く方法が多いでしょうか.例えば、すべての現在の文字列を探して、前に歩いて、ずっと等しいかどうかを見て、最後にサブ列の先頭に歩いて、もちろんこれは最も愚かです.この列は規則的であるため,一般に見られるKMPは最適化されている.ここでは依然として上記の表の一節を用いて例を挙げると、位置i=0から14は以下のように、私がつけた括弧は問題を説明するために使われているだけである:(a g c t a g c)(a g c t a g c)t私たちはこの段を見ることができ、最後のtの前の対称度はそれぞれ:1,2,3,4,5,6,7であり、最後から2番目のcは前に7文字対称であるため、対称は7である.しかし最後にこのtは前の対称度next値を継承しないので,このtの対称性は再び求めなければならない.ここでは主にいくつかの事実を明らかにしなければならない.1、tに対称性があるなら、対称度は前のcの対称度より小さいに違いない.だから、もっと小さい対称を探すのは説明するまでもない.大きくなれば、tは前の対称性を受け継ぐだろう.2、より小さな対称を探すには、対称内部に必ずサブ対称が存在し、このtはサブ対称の直後になければならない.
上の理論から,次の接頭辞next配列の解アルゴリズムを得ることができる.
この説明により,KMPのnext求法原理が理解できると推定され,残りは簡単である.私自身も少し気絶して、本当にあれらの数学の公式が好きではありませんて、だからイメージの論理の思惟の方法でまとめました.
KMPアルゴリズムには、接頭辞配列と呼ばれる配列もあれば、next配列と呼ばれる配列もあり、各サブ列には固定的なnext配列があり、文字列マッチング中に不整合になった場合に数文字前にジャンプできることを記録しています.もちろん、サブ列の対称度も記述されています.程度が高いほど、値が大きくなります.もちろん、前に再マッチングの機会が現れる可能性があります.このnext配列の求め方はKMPアルゴリズムの鍵ですが、よく理解できません.私はここで通俗的な言葉で説明します.他のところに数学の公式が導き出しているのを見て、卵が痛くて、この文章は数学の公式を見るのが好きではなく、KMPアルゴリズムを理解したい学生にしか貢献していません.
1、一例で説明すると、以下はサブストリングのnext配列の値であり、このサブストリングの対称度が高いことがわかるので、next値はいずれも大きい.
位置i:>0 1 2 3 4 5 6 7 9 10 11 12 13 14 15接頭辞next[i]:>0 0 0 0 1 2 3 1 3 4 5 6 7 4 0サブ列:>a g c t a g c a g c t a g c t g c t g
次の対称は中心対称ではなく、abccbaではなくabcabcのような中心文字ブロック対称であることを明らかにします.(1)対称列を1つずつ検索する.
これは簡単です.私たちはこのサブストリングをループして、前の1文字、前の2文字、3つ...i個から最後の15個まで見ます.1つ目のaは対称性がないので、対称度0の前の2つのagは対称性がないので、0の順に前の0-4を類推しても同じように0の前の5つのagctaで、この列に1つのaが等しいことが見えます.だから、対称度は1の前の6つのagctagで、agとagの対成が見えます.対称度は2です.ここで注意します.そう思うと、プログラミングはどうやって実現しますか.a、前の文字の前の文字の対称度が0の場合、現在の文字とサブ列の最初の文字を比較する限り、次のルールに従います.これはよく理解して、前はすべて0で、説明はすべて非対称で、もし1つの文字をプラスしたら、対称にするならば最大で現在のと最初の対称です.例えばagctaという中のtは0で、後ろのaの対称度は最初の文字aに等しいかどうかを見るだけです.
b、この推理によって、私たちは1つの法則をまとめることができて、前が0であるだけではなくて、もし前の1つの文字のnext値が1であれば、私たちは現在の文字と子列の2番目の文字を比較して、前が1であるため、前の文字がすでに1番目の文字と等しくなったことを説明して、もしこれがまた2番目の文字と等しくなったら、対称の程度が2であることを説明します.2文字が対称になった.例えば上のagctag、最後から2番目のaのnextは1で、それが1番目のaと対称であることを説明して、それから私たちは最後のgを2番目のgと比較して、また等しくて、自然対称成都は累積して、2です.
c、上の推理に従って、ずっと等しければ、ずっと积み重ねて、ずっと押してもいいですよ.ここまで押すのは少しも难しいでしょう.もし难しいと思ったら、私が书いたのが失败したことを意味します.もちろんそんなにうまく対称になるわけではありません.次が等しくないと、前の対称性を継承できないことを説明します.このような状況はそんなに対称性がないことを説明するしかありませんが、対称性がないとは説明できません.だから、このような状況に遭遇したら、もう一度考えなければなりません.これも難点です.
(2)対称性を振り返る
ここではもう前を継承することはできませんが、対称成都を探していますか.最も愚かな方法はサブ関数を書くことはできません.この文字列の最大対称度を探して、どのように書く方法が多いでしょうか.例えば、すべての現在の文字列を探して、前に歩いて、ずっと等しいかどうかを見て、最後にサブ列の先頭に歩いて、もちろんこれは最も愚かです.この列は規則的であるため,一般に見られるKMPは最適化されている.ここでは依然として上記の表の一節を用いて例を挙げると、位置i=0から14は以下のように、私がつけた括弧は問題を説明するために使われているだけである:(a g c t a g c)(a g c t a g c)t私たちはこの段を見ることができ、最後のtの前の対称度はそれぞれ:1,2,3,4,5,6,7であり、最後から2番目のcは前に7文字対称であるため、対称は7である.しかし最後にこのtは前の対称度next値を継承しないので,このtの対称性は再び求めなければならない.ここでは主にいくつかの事実を明らかにしなければならない.1、tに対称性があるなら、対称度は前のcの対称度より小さいに違いない.だから、もっと小さい対称を探すのは説明するまでもない.大きくなれば、tは前の対称性を受け継ぐだろう.2、より小さな対称を探すには、対称内部に必ずサブ対称が存在し、このtはサブ対称の直後になければならない.
上の理論から,次の接頭辞next配列の解アルゴリズムを得ることができる.
void SetPrefix(const char *Pattern, int prefix[])
{
int len=CharLen(Pattern);// 。
prefix[0]=0;
for(int i=1; i<len; i++)
{
int k=prefix[i-1];
// ，k=0 ，Pattern[i] != Pattern[k] ， ，
while( Pattern[i] != Pattern[k] && k!=0 )
k=prefix[k-1]; //
if( Pattern[i] == Pattern[k])// ， ， ++
prefix[i]=k+1;
else
prefix[i]=0; // ， ， 0
}
}この説明により,KMPのnext求法原理が理解できると推定され,残りは簡単である.私自身も少し気絶して、本当にあれらの数学の公式が好きではありませんて、だからイメージの論理の思惟の方法でまとめました.