正規表現を使ったアプローチについて

Question

プログラミング初学者です

https://www.hackerrank.com/challenges/re-findall-re-finditer/problem

例えばこの問題を解こうとしたときに

import re
m = re.findall(r'[^aiueoAIUEO][aiueoAIUEO]{2,}[^aiueoAIUEO]', input())
if len(m) == 0:
		print("-1")
else:
	for i in m:
		print(i[1:-1])

まずこのようなコードで解けると思ったのですが、これだと例えば
abaabaabaabaae
のように探したい文字列が連続したときに後の文字列がアウトプットされないという問題があります

また、同様に
https://www.hackerrank.com/challenges/the-minion-game/problem
この問題を正規表現を使って解けないかと考えたのですが（discussionをチラッと見ると全然使ってはいなかったのですが）、最小単位でfindallを使っても、特定の文字列が見つかると次の文字を読み込んでしまい組み合わせは読み込めないという問題があります

import re

print(re.findall(r'[^AIUEO]+?', input()))

>>['B', 'N', 'N']

正規表現を使うときに、組み合わせをすべて上手く読み取れるようなアプローチがあれば教えていただきたいです
よろしくお願いします

Answer 1

前半については、すべての母音以外の文字を２つに繰り返してから、findallすればよいかと。
もっとスマートな方法はある可能性が高いですが。

import re
s = input()
cs = set(re.findall(r'[^aiueoAIUEO]', s))
for c in cs:
    s = s.replace(c, c*2)
m = re.findall(r'[^aiueoAIUEO][aiueoAIUEO]{2,}[^aiueoAIUEO]', s)
if len(m) == 0:
        print("-1")
else:
    for i in m:
        print(i[1:-1])

こっちのほうが速いですね。

import re
s = input()
s = re.sub(r'[^aiueoAIUEO]{1,}', 'zz', s)
m = re.findall(r'[^aiueoAIUEO][aiueoAIUEO]{2,}[^aiueoAIUEO]', s)
if len(m) == 0:
        print("-1")
else:
    for i in m:
        print(i[1:-1])

---

後半は、ただの数え上げなので、正規表現を使わないかと。
例えば、A***なら[A, A*, A**, A***]4種類を数え上げるだけなので。
どうしても全パターンを一度出力したいのならitertoolsのcombinationsを使えば良いです。

import itertools

def list_of_combs(s):
    combs = [s[i:j] for i,j in itertools.combinations(list(range(len(s)))+[None], 2)]
    return combs
        
print(list_of_combs(input()))
#['B', 'BA', 'BAN', 'BANA', 'BANAN', 'BANANA', 'A', 'AN', 'ANA', 'ANAN', 'ANANA', 'N', 'NA', 'NAN', 'NANA', 'A', 'AN', 'ANA', 'N', 'NA', 'A']

---

以下チラ裏かもですが。
アルゴリズムに興味があるのかわからないのですが、全パターンを一度展開してしまうと、計算時間・計算メモリともに厳しいものがあります。
計算時間としては計算のオーダーが重要かと思います。

1. 上の例で、A***を見たら直ちにそれは4を足せば良いと分かればオーダーは文字列の長さにかかわらず1となります。O(1)と表記します。
2. それに対して[A, A*, A**, A***]と展開すると、文字列の長さM個だけ増えます。これはO(M)というやつです。

この外側に、上の問題の場合文字列の先頭を走査するのに、Sの長さN回行う必要があります。

1. それぞれの部分文字列の数え上げがO(1)であれば、全体でO(N)、
2. 部分文字列の数え上げがO(N)であれば、全部合わせて数え上げるのにO(N^2)の計算量がかかります。

問題ではSの長さの上限が10^6でしたので、O(N)のアルゴリズムでは10^6回、O(N^2)のアルゴリズムでは10^12回演算が発生します。
高性能なCPUでも4.5GHzなどなので一秒あたり10^9の演算しかできません。
比較してみると前者のアルゴリズムでは1秒以内に終わるのに対して、後者のアルゴリズムでは数分かかります。