回答編集履歴

1

追加コードへの回答

2021/06/15 06:14

投稿

ppaul
ppaul

スコア24670

test CHANGED
@@ -9,3 +9,57 @@
9
9
 
10
10
 
11
11
  もしも、関数sptが再帰呼び出しをしていなければ、StarAの呼び出し一回について、関数sptは一回呼び出されているので、数える必要はないのではないでしょうか。
12
+
13
+
14
+
15
+ 再帰呼び出しの場合はいろいろな方法があります。
16
+
17
+ 追加されたコードをなるべく活かすなら以下です。
18
+
19
+
20
+
21
+ ```python
22
+
23
+ def spt(L,R,LCP,lcpstar,cnt=[0], reset=False):
24
+
25
+ if reset:
26
+
27
+ cnt[0] = 0
28
+
29
+ cnt[0] += 1
30
+
31
+ print(str(cnt[0]) + "回目の呼び出し")
32
+
33
+ if R-L > 1:
34
+
35
+ M = int((L+R)/2)
36
+
37
+ vL, lcpstar = spt(L, M, LCP, lcpstar)
38
+
39
+ vR, lcpstar = spt(M, R, LCP, lcpstar)
40
+
41
+ v = min(vL, vR)
42
+
43
+ elif R-L == 1:
44
+
45
+ v = LCP[L]
46
+
47
+
48
+
49
+ lcpstar[tuple([L,R])] = v
50
+
51
+ lcpstar[tuple([R,L])] = v
52
+
53
+ return v, lcpstar
54
+
55
+
56
+
57
+ def StarA(LCP):
58
+
59
+ lcpstr={}
60
+
61
+ v, lcpstr=spt(0,len(LCP)-1, LCP, lcpstr, reset=True)
62
+
63
+ return lcpstr
64
+
65
+ ```