前半については、すべての母音以外の文字を2つに繰り返してから、findallすればよいかと。
もっとスマートな方法はある可能性が高いですが。
python
1import re
2s = input()
3cs = set(re.findall(r'[^aiueoAIUEO]', s))
4for c in cs:
5 s = s.replace(c, c*2)
6m = re.findall(r'[^aiueoAIUEO][aiueoAIUEO]{2,}[^aiueoAIUEO]', s)
7if len(m) == 0:
8 print("-1")
9else:
10 for i in m:
11 print(i[1:-1])
こっちのほうが速いですね。
python
1import re
2s = input()
3s = re.sub(r'[^aiueoAIUEO]{1,}', 'zz', s)
4m = re.findall(r'[^aiueoAIUEO][aiueoAIUEO]{2,}[^aiueoAIUEO]', s)
5if len(m) == 0:
6 print("-1")
7else:
8 for i in m:
9 print(i[1:-1])
後半は、ただの数え上げなので、正規表現を使わないかと。
例えば、A***
なら[A, A*, A**, A***]
4種類を数え上げるだけなので。
どうしても全パターンを一度出力したいのならitertoolsのcombinationsを使えば良いです。
python
1import itertools
2
3def list_of_combs(s):
4 combs = [s[i:j] for i,j in itertools.combinations(list(range(len(s)))+[None], 2)]
5 return combs
6
7print(list_of_combs(input()))
8#['B', 'BA', 'BAN', 'BANA', 'BANAN', 'BANANA', 'A', 'AN', 'ANA', 'ANAN', 'ANANA', 'N', 'NA', 'NAN', 'NANA', 'A', 'AN', 'ANA', 'N', 'NA', 'A']
以下チラ裏かもですが。
アルゴリズムに興味があるのかわからないのですが、全パターンを一度展開してしまうと、計算時間・計算メモリともに厳しいものがあります。
計算時間としては計算のオーダーが重要かと思います。
- 上の例で、
A***
を見たら直ちにそれは4を足せば良いと分かればオーダーは文字列の長さにかかわらず1となります。O(1)と表記します。
- それに対して
[A, A*, A**, A***]
と展開すると、文字列の長さM個だけ増えます。これはO(M)というやつです。
この外側に、上の問題の場合文字列の先頭を走査するのに、Sの長さN回行う必要があります。
- それぞれの部分文字列の数え上げがO(1)であれば、全体でO(N)、
- 部分文字列の数え上げがO(N)であれば、全部合わせて数え上げるのにO(N^2)の計算量がかかります。
問題ではSの長さの上限が10^6でしたので、O(N)のアルゴリズムでは10^6回、O(N^2)のアルゴリズムでは10^12回演算が発生します。
高性能なCPUでも4.5GHzなどなので一秒あたり10^9の演算しかできません。
比較してみると前者のアルゴリズムでは1秒以内に終わるのに対して、後者のアルゴリズムでは数分かかります。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。