regex - すべての一致を見つけるためにNFAまたはDFAベースの正規表現マッチングアルゴリズムを実装する方法は?

Question

試合は重複する可能性があります。

ただし、同じ位置から始まる複数の一致が見つかった場合は、短いものを選択してください。

たとえば、文字列"abcabdcd"で正規表現部分"a.*d"を見つけるには、答えは { "abcabd" , "abd" } になります。また、「abcabdcd」と「abdcd」は含めないでください。

Answer 1

ほとんどのREエンジンは、デフォルトでREと1回だけ一致し、貪欲に一致します。それらを中心に構築された標準の反復戦略は、前回の一致の終了後に検索を再開する傾向があります。それ以外のことをするには、いくつかの追加のトリックが必要です。（このコードはTclですが、他の多くの言語で複製できるはずです。）

proc matchAllOverlapping {RE string} {
    set matches {}
    set nonGreedyRE "(?:${RE}){1,1}?"
    set idx 0
    while {[regexp -indices -start $idx $nonGreedyRE $string matchRange]} {
        lappend matches [string range $string {*}$matchRange]
        set idx [expr { [lindex $matchRange 0] + 1 }]
    }
    return $matches
}
puts [matchAllOverlapping a.*d abcabdcd]

Answer 2

この関数はかなり非効率的ですが、問題を解決します:

def find_shortest_overlapping_matches(pattern, line):
        pat=re.compile(pattern)
        n=len(line)
        ret=[]
        for start in xrange(0, n):
                for end in xrange(start+1, n+1):
                        tmp=line[start:end]
                        mat=pat.match(tmp)
                        if mat is not None:
                                ret.append(tmp)
                                break
        return ret

print find_shortest_overlapping_matches("a.*d", "abcabdcd")

出力：

['abcabd', 'abd']

範囲は、パターンに少なくとも 1 文字が含まれ、空の文字列と一致しないことを前提としています。さらに、?パフォーマンスを向上させ、内部ループを回避するために、パターンを非貪欲に一致させるために を使用することを検討する必要があります。