文字列アルゴリズムのまとめ
文字列はプログラミング言語でテキストを表すデータの種類です.多くの文字列の問題、例えばDP、統計案数などは、基本的には文字列マッチング問題を解決しなければなりません.
本編では主に5つのアルゴリズムを説明します.ハッシュ法(最も直感的な方法) KMPアルゴリズム(基本的な方法) 拡張KMPアルゴリズム(KMPアルゴリズムの拡張) Manacherアルゴリズム(文字列の問題を解決する) AC自動機(Trie+KMP) アルゴリズムの基礎概念から切り込み、逐次的に詳細なアルゴリズム処理と実現を行い、システム学習を支援します.その間には経典の例題を交えて解説したり、結合を練習したりして、快速かつ効率的に文字列に関する知識を把握して、実際のプログラミングの中で自由自在に使えます.
文字列の最も一般的な応用は文字列のマッチングです.
現在の競争においてこのような問題を解決する方法は主に以下の通りです.ハッシュ KMP サフィックス配列/サフィックスツリー/サフィックス自動機 ハッシュ:は1つの文字列を1つの数字に変換し、その後の各比較は、2つの文字列が等しいかどうかを比較し、2つの数字が等しいかを比較するだけでよい. は最も簡単で直感的で、実現しやすく、開拓しやすいです. KMPアルゴリズム:線形のアルゴリズム. 本質は、テンプレート・ストリング自体の情報を利用して、マッチング時の冗長比較を減少させ、優れた時間複雑度を達成することである. 拡張KMPアルゴリズム:は、この方法がKMPアルゴリズムと異なる点に注目する. は、対称性を利用して、時間の複雑さを低減する. Manacherアルゴリズム:は特に文字列の問題を解決するために用いられます. は、対称性を利用して、時間の複雑さを低減する. AC自動機:は辞書ツリー(Trie)とKMPとを結合して、この2つの組み合わせはその後、「マルチストリング」の問題を解決することができ、前の4つのアルゴリズムはすべてシングルストリング問題を解決するために用いられる.辞書の木には複数の文字列が格納され、KMPの思想を加えるとAC自動機が得られます. TrieツリーとKMPの組み合わせは、1つの列または複数の列の整合問題を解決することができる. 1.ハッシュ表
ハッシュ・テーブルの導入:線形テーブル(1,75,324,43,1353,90,46)を格納し使用する場合、これらの数は1つのアレイA［1…7］を使用して順次記憶される.しかし、このような記憶構造は、照会アルゴリズムにO(n)の時間オーバヘッドをもたらす.
A順序に対しては、二分割照会法を使用して、時間の複雑さをO(logn)に変えても空間的に時間を切り替える方法があり、配列A［1…1353］で各数が現れるかどうかを表し、検索時間の複雑さをO(1)に変えても良いが、空間的なオーバーヘッドは大きくなる.
前の方法を最適化して、ハッシュ関数h(key)=key%23.(1,75,324,43,1353,90)-』(1,6,2,20,19,21)を作成します.A[0...22]配列を使えば、すぐに照会できます.このような線形表の構造をハッシュテーブルと呼ぶ.
ハッシュ・テーブルの基本原理は、比較的スケールの大きいアレイAで要素を格納することであることが分かる.
一つの関数hを設計して、記憶する線形表の各要素nodeに対して、一つのキーワードkeyを取り、関数値h(key)を算出して、この値を下付きとして、nodeをA[h(key)で記憶する.最も一般的なhはモード関数であり、つまりmを選択し、令h(key)＝key%mとなる.
ハッシュ・テーブルの衝突:2つのkey:k 1が存在し、k 2はh(k 1)＝h(k 2)を可能にし、このときも「衝突」を発生させる.
衝突を解決するには多くの方法があります.は、別の関数IでI(k 1)、I(k 2)を計算し、新しい位置を見つけることができる. は、Aの各要素にチェーンを一つずつ預けてもいいです.h(k 1)＝h(k 2)に対して、この二つのnodeをA[h(k 1)]のチェーンに接続してもいいです. 競合を解決するために第二の方法を使用すると仮定します.はh(key)を計算して、nodeをA[h(key)チェーンに挿入します.クエリ要素(node,key): はh(key)を計算して、もしA[h(key)が空ならば、nodeが存在しないと説明します.さもなければA[h(key)チェーンを巡回して、nodeを探します. ハッシュテーブルのコード実装:
X[1...4]をすでに知っているのは[-T,T]の整数で、満足方程式を求めます.AX[1]+BX[2]+CX[3]+DX[4]=P.の解はいくつのグループがありますか?注:P≦1剁ᙽ?????、?B|、?C?C、?C、q 10.C、q 10.C、q 10.C、q 10、q 10、124q 10、124q 10、q 10、q 10、q 10、q 10、q 10、q 10、q 104;q、q、q 104、q.B T≦500.
最も直感的な方法は、X［1…4］を列挙し、時間複雑度O(n 4)O(n＾｛4｝)O(n 4)を列挙する.適切に最適化し、X［1…3］を列挙した後、実際にはX［4］が確定しました.時間複雑度O(n 3)O(n^｛3｝)O(n 3)です.引き続き最適化し、meet in the middle戦略を採用する:を列挙しながらX[1],X[2] を列挙する.は、X［4］、X［3］を列挙しながら、どのようなスキームが方程式を構成するかを確認する. エニュメレート・X[1],X[2]を計算し、P-AX[1]-BX[2]を算出し、この値を一つのハッシュ・テーブルに格納し、統計回数に注意する.このステップの時間複雑度O(n 2)O(n^｛2｝)O(n 2)です.その後、X［3］、X［4］を列挙して、CX［3］＋DX［4］を算出して、ハッシュ・テーブルの中でこの値を検索すると何回か出現します.回数を答えに盛り込むと、このステップは複雑度O(n 2)O(n^｛2｝O(n 2)ですので、トータルの時間複雑度はO(n 2)O(n^｛2｝O(n 2)です.
文字列のハッシュ:n個の長さがLの文字列であると仮定し、質問の中に最大いくつかの文字列が等しい.2つの長さがLの文字列が等しいかどうかを直接比較します.複雑さはO(L)です.したがって、列挙O(n2)O(n^{2})O(n 2)で文字列を比較する必要があり、時間複雑度O(n 2 L)O(n^{2}L)O(n 2 L)である.各文字列を一つのハッシュ関数で整数にマッピングする場合.問題は一つのシーケンスの共通数を探すことになります.時間複雑さはO(n L)O(nL)O(nL)O(nL)に変化する.
設計された良好な文字列ハッシュ関数は、O(L)O(L)O(L)O(L)の時間的複雑度前処理を使用し、その後、この文字列のサブストリングのハッシュ値を取得する度に、O(1)O(1)O(1)の時間だけが必要となる.
ここでは重点的にBKDRHashを紹介します.
BKDRHash:BKDRHashの基本思想は一つの文字列を一つのk進数として処理することです.
注意:h a[y]=s[1]k y−1+s[2]k y−−2+.....+s[x−1]k−y−−−x+1+s[x]k+1+s[x]k+k+y+++++s+++s+s[y]h a[y]===s+k｛y-1｝+s[2]k｛k｛k｛+y+2｝+s+s+s+++++s+++s+++++s++++s+++++s+++++s+s+++++y++++s++++++++y++++y++++s++s+y++y++++2+…+s[x−1]k y−x+1+s[x]ky−x+…+s[y]
注意:h a[x−1]=s[1]k−2＋s[2]k x−3+..+s[x−1]ha[x-1]=s[1]k^{x-2}+s[2]k^^{x-3}＋s[2]、{x-3}＋s[x−1]ha[x−1]==s[1]kx 2+s+2[/x]
私たちが要求するs[x...y]のハッシュ値はs[x]k y−x+...+s[y]s[x]s[/x]k^{y-x}＋s[y]s[y]s[y]s[x]ky−x＋…s[y]である.
s[x.....y]=h a[y]a[x−1]k y−x＋1 s[x...y]=ha[y]-ha[x-1]k^{y-x+1}s[x...]=ha[y]−ハ[x−1]ky−x＋1.
したがって、ha配列とkのべき乗回を前処理し、毎回s［x…y］のハッシュ値を問い合わせると、O(1)の時間しかかかりません.
勉強しながら練習します.阿軒さんは紙に2つの文字列を書いて、それぞれAとBと書きます.データ構造とアルゴリズム課で学んだ知識を利用して、彼は簡単に「文字列Aの任意の位置からのサフィックス部分列」と「文字列B」のマッチングの長さを求めました.しかし、阿軒は勉強好きのクラスメートです.彼はあなたにQ個の問題を提出しました.各問題の中で、彼はあなたに整数xを与えました.彼にどのぐらいの位置があるか教えてください.「文字列Aはこの位置から始まるサフィックスの列」とBのマッチングの長さはxにぴったりです.例えば、A=ab cde、B=abがあれば、Aはabcde、bcde、cde、de、eの6つのサフィックスサブストリングがあり、それらはB=abとのマッチング長さはそれぞれ:1、2、0、0、0、0、0、0.です.したがって、Aは4つの位置がBとのマッチング長されています.Q\leq 200000.1≦N,M,Q≦200000.
核心の問題は:2つの文字列A、Bを与えます.Aの各拡張子列とBの最長共通プレフィックスを求める.標準的なやり方はKMPを拡張して、時間の複雑さは線形です.まずHashを使ってみましょう.
前に述べたように、O(n)前処理、O(1)処理におけるサブストリングのハッシュ値を使用することができる.
文字列A[i...n]と文字列B[1...m]の一番長い共通プレフィックスを求めますか?二点です二分長midはA[i...i+mid-1]とB[i...mid]のハッシュ値を計算して、比較は等しいですか?そのため、時間の複雑さはO(logn)です!
本編では主に5つのアルゴリズムを説明します.
文字列の最も一般的な応用は文字列のマッチングです.
現在の競争においてこのような問題を解決する方法は主に以下の通りです.
ハッシュ・テーブルの導入:線形テーブル(1,75,324,43,1353,90,46)を格納し使用する場合、これらの数は1つのアレイA［1…7］を使用して順次記憶される.しかし、このような記憶構造は、照会アルゴリズムにO(n)の時間オーバヘッドをもたらす.
A順序に対しては、二分割照会法を使用して、時間の複雑さをO(logn)に変えても空間的に時間を切り替える方法があり、配列A［1…1353］で各数が現れるかどうかを表し、検索時間の複雑さをO(1)に変えても良いが、空間的なオーバーヘッドは大きくなる.
前の方法を最適化して、ハッシュ関数h(key)=key%23.(1,75,324,43,1353,90)-』(1,6,2,20,19,21)を作成します.A[0...22]配列を使えば、すぐに照会できます.このような線形表の構造をハッシュテーブルと呼ぶ.
ハッシュ・テーブルの基本原理は、比較的スケールの大きいアレイAで要素を格納することであることが分かる.
一つの関数hを設計して、記憶する線形表の各要素nodeに対して、一つのキーワードkeyを取り、関数値h(key)を算出して、この値を下付きとして、nodeをA[h(key)で記憶する.最も一般的なhはモード関数であり、つまりmを選択し、令h(key)＝key%mとなる.
ハッシュ・テーブルの衝突:2つのkey:k 1が存在し、k 2はh(k 1)＝h(k 2)を可能にし、このときも「衝突」を発生させる.
衝突を解決するには多くの方法があります.
struct node{
int next, info;
}hashNode[N];
int tot; //
int h[M]; // -1
//
void insert(int key, int info){
int u = key % M;
hashNode[tot] = (node){h[u], info};
hu] = tot ++;
}
//
int find(int key, int info){
int u = key % M;
for(int i=h[u]; i!=-1; i=hashNode[i].next){
if (hashNode[i].info == info)
return 1;
}
return 0;
}
X[1...4]をすでに知っているのは[-T,T]の整数で、満足方程式を求めます.AX[1]+BX[2]+CX[3]+DX[4]=P.の解はいくつのグループがありますか?注:P≦1剁ᙽ?????、?B|、?C?C、?C、q 10.C、q 10.C、q 10.C、q 10、q 10、124q 10、124q 10、q 10、q 10、q 10、q 10、q 10、q 10、q 104;q、q、q 104、q.B T≦500.
最も直感的な方法は、X［1…4］を列挙し、時間複雑度O(n 4)O(n＾｛4｝)O(n 4)を列挙する.適切に最適化し、X［1…3］を列挙した後、実際にはX［4］が確定しました.時間複雑度O(n 3)O(n^｛3｝)O(n 3)です.引き続き最適化し、meet in the middle戦略を採用する:
文字列のハッシュ:n個の長さがLの文字列であると仮定し、質問の中に最大いくつかの文字列が等しい.2つの長さがLの文字列が等しいかどうかを直接比較します.複雑さはO(L)です.したがって、列挙O(n2)O(n^{2})O(n 2)で文字列を比較する必要があり、時間複雑度O(n 2 L)O(n^{2}L)O(n 2 L)である.各文字列を一つのハッシュ関数で整数にマッピングする場合.問題は一つのシーケンスの共通数を探すことになります.時間複雑さはO(n L)O(nL)O(nL)O(nL)に変化する.
設計された良好な文字列ハッシュ関数は、O(L)O(L)O(L)O(L)の時間的複雑度前処理を使用し、その後、この文字列のサブストリングのハッシュ値を取得する度に、O(1)O(1)O(1)の時間だけが必要となる.
ここでは重点的にBKDRHashを紹介します.
BKDRHash:BKDRHashの基本思想は一つの文字列を一つのk進数として処理することです.
int k = 19, M = 1e9+7;
int BKDRHash (char *str){
int ans = 0;
for (int i=0; str[i]; i++){
ans = (1LL*ans*k +str[i]) % M;
}
return ans;
}
ha[0] = 0;
for (int i=1; i<=n; i++){
ha[i] = (ha[i-1]*k + str[i]) % M;
}
注意:h a[y]=s[1]k y−1+s[2]k y−−2+.....+s[x−1]k−y−−−x+1+s[x]k+1+s[x]k+k+y+++++s+++s+s[y]h a[y]===s+k｛y-1｝+s[2]k｛k｛k｛+y+2｝+s+s+s+++++s+++s+++++s++++s+++++s+++++s+s+++++y++++s++++++++y++++y++++s++s+y++y++++2+…+s[x−1]k y−x+1+s[x]ky−x+…+s[y]
注意:h a[x−1]=s[1]k−2＋s[2]k x−3+..+s[x−1]ha[x-1]=s[1]k^{x-2}+s[2]k^^{x-3}＋s[2]、{x-3}＋s[x−1]ha[x−1]==s[1]kx 2+s+2[/x]
私たちが要求するs[x...y]のハッシュ値はs[x]k y−x+...+s[y]s[x]s[/x]k^{y-x}＋s[y]s[y]s[y]s[x]ky−x＋…s[y]である.
s[x.....y]=h a[y]a[x−1]k y−x＋1 s[x...y]=ha[y]-ha[x-1]k^{y-x+1}s[x...]=ha[y]−ハ[x−1]ky−x＋1.
したがって、ha配列とkのべき乗回を前処理し、毎回s［x…y］のハッシュ値を問い合わせると、O(1)の時間しかかかりません.
勉強しながら練習します.阿軒さんは紙に2つの文字列を書いて、それぞれAとBと書きます.データ構造とアルゴリズム課で学んだ知識を利用して、彼は簡単に「文字列Aの任意の位置からのサフィックス部分列」と「文字列B」のマッチングの長さを求めました.しかし、阿軒は勉強好きのクラスメートです.彼はあなたにQ個の問題を提出しました.各問題の中で、彼はあなたに整数xを与えました.彼にどのぐらいの位置があるか教えてください.「文字列Aはこの位置から始まるサフィックスの列」とBのマッチングの長さはxにぴったりです.例えば、A=ab cde、B=abがあれば、Aはabcde、bcde、cde、de、eの6つのサフィックスサブストリングがあり、それらはB=abとのマッチング長さはそれぞれ:1、2、0、0、0、0、0、0.です.したがって、Aは4つの位置がBとのマッチング長されています.Q\leq 200000.1≦N,M,Q≦200000.
核心の問題は:2つの文字列A、Bを与えます.Aの各拡張子列とBの最長共通プレフィックスを求める.標準的なやり方はKMPを拡張して、時間の複雑さは線形です.まずHashを使ってみましょう.
前に述べたように、O(n)前処理、O(1)処理におけるサブストリングのハッシュ値を使用することができる.
文字列A[i...n]と文字列B[1...m]の一番長い共通プレフィックスを求めますか?二点です二分長midはA[i...i+mid-1]とB[i...mid]のハッシュ値を計算して、比較は等しいですか?そのため、時間の複雑さはO(logn)です!
ll getha (int x, int y){
return ha[y] - ha[x-1] * p[y-x+1];
}
ll gethb (int x, int y){
return hb[y] - hb[x-1] * p[y-x+1];
}
int main() {
scanf("%d%d%d", &n, &m, &);
scanf("%s", a+1);
scanf("%s", b+1);
p[0] = 1;
for (int i=1; i<=max(n,m); i++) p[i] = p[i-1] * P;
for (int i=1; i<=n; i++) ha[i] = ha[i-1] * P + a[i];
for (int i=1; i<=m; i++) hb[i] = hb[i-1] * P + b[i];
for (int i=1; i<=n; i++){
int L = 1, R = min(m, n-i+1), mid;
while (L <= R) {
mid = (L + R) >> 1;
if (getha(i, i+mid-1) == gethb(1, mid)){
L = mid + 1;
}else {
R = mid - 1;
}
}
cnt[R]++;
}
}