C：正規表現の最適化|状態を保存する

"AAAAAAAABBBBBBB"と "AAAAAAAACCCCCCCCCCC"で検索したいとします。パターン "（AB | AC）"を検索します。C：正規表現の最適化|状態を保存する

「AAAAAAAA」の部分を検索してから[B ..]と[C ..]の部分を別々に検索した後で、検索の状態を保存する方法はありますか？だから私は[A ..]で一度だけ検索する必要があります。

私は、より明確な短い疑似コードの例を書いています。

ステップ1：

pattern = "(AB|AC)" 
match("AAAAAAAA", pattern) 
save_state()

ステップ2：

match("BBBBBBB", pattern)

検索マッチ "AB"

ステップ3が必要です。

restore_state() 
match("CCCCCCCCCCC", pattern)

見つけなければならない試合「AC "

2012-02-10 AkaBkn

これは私には意味がありません。彼らは2つの異なる場所で、異なる文字列です。どのように結果を保存すると、他の人を助けるでしょうか？ – Oliver

'A（B | C）'または 'A [BC]'を意味しますか？ – Gumbo

いいえ、最初のx文字は同じです（A）。それらが非常に大きい場合、私はそれらを一度だけ検索したいと思います。 Aシーケンスの終わりに保存された状態はAとなり、Bと続きます...それはBシーケンスと2回続けて同じものを生成します。 – AkaBkn

（実際の）NFA/DFAアプローチ（RE2など）を使用する正規表現フレーバを使用する場合は、すべての入力文字が1回だけ使用されるため、何も保存する必要はありませんよくなる）。

フレーバーがバックトラックアルゴリズムを使用している場合は、運がよいかもしれません。これらのエンジンのいくつかは、あなたが、それは（それが許可されています場合）することができ、あなたの場合はそう

（{1}は、任意の数量詞もよい）(?>x)またはx{1}+を使用して非バックトラッキング（別名所有）一部を紹介させ

(?>A)(B|C)

または

A{1}+(B|C)

2015-06-17 19:36:52

答えて