文字列のボーダーとは、接尾辞でもある真の接頭辞のことです。ボーダーがあれば、マッチングの処理は不一致の後でもそれまでの作業を再利用できます。候補のボーダーを伸ばせなければ、テキストを最初から比べ直すのではなく、そのボーダーのボーダーを試してください。接頭辞関数の表には、これらの戻り先の長さが記録されます。
重なる一致があると、戻りの規則がはっきり見えます。ababaの中でabaに一致した後、最後のaから次の一致を始められます。一致した長さを0に戻すと、その出現を見落とします。回文の構築では、入力の文字集合にない区切り文字で文字列とその逆順を連結し、同じボーダーの表を使います。
文字列の問題がすべてその表を必要とするわけではありません。入力の大きさが限られた回文区間の課題では、中心から広げる方法がわかりやすい2乗時間の解法です。一方、制限付きの式のマッチングでは、2つの接頭辞に対する動的計画法を使います。それぞれの文法を正確に述べてください:このは直前の要素を繰り返すもので、混合の練習セットにある単独のワイルドカードのとは異なります。