この問題を解決するには、通常の列挙は機能しません。その漸近線は
O(t*s) になります。したがって、部分文字列検索タスクには、KMP (Knuth-Morris-Pratt) アルゴリズムが使用されます。
このアルゴリズムを実装するには、文字列プレフィックス関数が使用されます。これは長さ
n (strong>s) の数値の配列であり、各要素は最大長になります。部分文字列
s の最大の独自の接尾辞を、その接頭辞と一致させます。例:
<本体>
| ライン |
プレフィックス関数 |
メモ |
| アババブカブ |
0 0 1 2 3 4 0 1 2 |
|
| abcabcd |
0 0 0 1 2 3 0 |
|
| アバアブ |
0 1 0 1 2 2 3 |
|
O(n^3) 漸近線を持つ自明なプレフィックス関数アルゴリズム:
ベクトル<int> prefix_function (文字列 s) {
int n = (int ) s.length();
ベクトル<int>pi(n);
の (int i=0; i<n; ++i)
の (int k=0; k<=i; ++k)
if (s.substr(0,k) == s .substr(i-k+1,k))
pi[i] = k;
円周率を返します。
}
次に、次の形式の文字列に対するプレフィックス関数を作成する必要があります。 t + # + s。# は明らかにテキストに含まれていない区切り文字です。対応する区切り文字の後のプレフィックス関数の値を分析すると、結果の値が目的の部分文字列の長さに等しい場合、その出現が検出されることに注意してください。たとえば、文字列「abababcab」の場合、および目的の部分文字列「abab」の場合、プレフィックス関数は次のようになります。
0 0 1 2 0 1 2 3 4 3 4 0 1 2対応する文字列 s の要素を解析する必要があります。
1 2 3 4 3 4 0 1 2 - 値が 4 になるケースが 2 つあります ( 4th と 6th )。長さ t、 その結果、答えは 4 - 4 (長さ t) と書く必要があります。 = 0 および 6 - 4 = 2。これらが正しい答えであり、文字列「abab」が正しい答えであることがわかります。実際には、文字列「abababcab」の部分文字列です。位置0と2にあります。
プレフィックス関数を最適化した後 (詳細については こちら )、O(n) 漸近の最終アルゴリズムが得られます。
ベクトル<int> prefix_function (文字列 s) {
int n = (int ) s.length();
ベクトル<int>pi(n);
の (int i=1; i<n; ++i) {
int j = pi[i-1< /スパン>];
その間 (j > 0 && s[i] != s[j])
j = pi[j-1];
if (s[i] == s[j]) ++j;
pi[i] = j;
}
円周率を返します。
}
|
Z-関数
Z-function 文字列 S から - 配列 Z、その各要素は Z [i ] は、文字列 S 内の位置 i から始まる部分文字列の最長の接頭辞に等しく、文字列 全体の接頭辞でもあります>Z.ゼロ位置の Z 関数の値は、通常、ゼロまたは文字列全体の長さです。
難易度
O(|S| ^ 2) または O(|S|).
文字列 S の接頭辞関数 - 配列 P、その P[i] の各要素は、文字列 S 内の位置 < code>i から始まる部分文字列。これは、文字列 S 全体のサフィックスでもあります。 P-function の位置 0 の値は、通常、0 または文字列全体の長さです。
難易度
O(|S| ^ 2) または O(|S|).
Z関数とプレフィックス関数 for O(|S| ^ 2)を実装してみてください.
|
Z と関数プレフィックスの両方を使用して、O(|S|) の文字列内の部分文字列を見つけるための KMP(Knuth-Morris-Pratt) アルゴリズムを実装できます。このアルゴリズムの本質は次のとおりです。検索対象の文字列を、検索対象の文字列に帰属させます。これらの行の間に区切り文字、つまりどの行にも出現しない文字 (通常は #) を入れることが非常に望ましいです。
|