teratail header banner
teratail header banner
質問するログイン新規登録

回答編集履歴

1

追加コードへの回答

2021/06/15 06:14

投稿

ppaul
ppaul

スコア24672

answer CHANGED
@@ -3,4 +3,31 @@
3
3
  StarA(LCP)の呼び出しより後に置けば回数を数えることはできません。
4
4
  StarA(LCP)より前に置けば実行時エラーになります。
5
5
 
6
- もしも、関数sptが再帰呼び出しをしていなければ、StarAの呼び出し一回について、関数sptは一回呼び出されているので、数える必要はないのではないでしょうか。
6
+ もしも、関数sptが再帰呼び出しをしていなければ、StarAの呼び出し一回について、関数sptは一回呼び出されているので、数える必要はないのではないでしょうか。
7
+
8
+ 再帰呼び出しの場合はいろいろな方法があります。
9
+ 追加されたコードをなるべく活かすなら以下です。
10
+
11
+ ```python
12
+ def spt(L,R,LCP,lcpstar,cnt=[0], reset=False):
13
+ if reset:
14
+ cnt[0] = 0
15
+ cnt[0] += 1
16
+ print(str(cnt[0]) + "回目の呼び出し")
17
+ if R-L > 1:
18
+ M = int((L+R)/2)
19
+ vL, lcpstar = spt(L, M, LCP, lcpstar)
20
+ vR, lcpstar = spt(M, R, LCP, lcpstar)
21
+ v = min(vL, vR)
22
+ elif R-L == 1:
23
+ v = LCP[L]
24
+
25
+ lcpstar[tuple([L,R])] = v
26
+ lcpstar[tuple([R,L])] = v
27
+ return v, lcpstar
28
+
29
+ def StarA(LCP):
30
+ lcpstr={}
31
+ v, lcpstr=spt(0,len(LCP)-1, LCP, lcpstr, reset=True)
32
+ return lcpstr
33
+ ```