4

次のような単語のリストがあります。

l = """abc
dfg
hij
jih
gfd
cba
cbd
jip
gfe
jiw
cbw"""

このリストから単語のペアを見つけたいので、最初の単語は次のとおりです。

.(.)(.)

そして、2 番目の単語は次のとおりです。

\2\1.

したがって、\1 と \2 は最初の単語の文字を参照します。

私が思いつくことができる最高の正規表現は次のとおりです。

re.findall('(^.(?P<A>.)(?P<B>.)$)(?=.*(^(?P=B)(?P=A).$))', l, re.DOTALL | re.MULTILINE)

ただし、この検索で​​は一部のペアしか返されません (findall は重複しない結果のみを返すため...)。次に、肯定的な後読みアサーションを使用することを考えましたが、固定長の文字列でしか使用できません...

正規表現でこれを行う方法はありますか?

4

1 に答える 1

2

正規表現がこれを行うための良い方法であるとは思えません (特に Python では、Perl のように文字列に一致するすべての可能な方法を単純に取得することはできないため、文字列findallのすべてのプレフィックスを呼び出す必要があります)。簡単な代替手段は次のとおりです。

words = l.split()
pairs = set(frozenset((w1, w2)) for w1 in words for w2 in words 
                      if w1[1:] == w2[1::-1])

結果:

>>> map(tuple, pairs)
[('hij', 'jip'), 
 ('abc', 'cbd'), 
 ('dfg', 'gfd'), 
 ('dfg', 'gfe'), 
 ('jiw', 'hij'), 
 ('hij', 'jih'), 
 ('abc', 'cbw'), 
 ('abc', 'cba')]

また、最初のパスで単語の接頭辞を辞書に保存し、2 番目のパスで関連付けを構築することで、これを非常に迅速に解決することもできます。

from collections import defaultdict

prefixes = defaultdict(list)
for w in words:
    prefixes[w[1::-1]].append(w) 
pairs = set(frozenset((w1, w2)) for w1 in words for w2 in prefixes[w1[1:]])

このパフォーマンスは、正規表現エンジンに勝るものはありません。

于 2012-05-01T19:09:42.340 に答える