回答編集履歴
2
コード追加
test
CHANGED
|
@@ -110,7 +110,7 @@
|
|
|
110
110
|
|
|
111
111
|
result.append(s)
|
|
112
112
|
|
|
113
|
-
else: # len(s) が MAX_LENGTH を
|
|
113
|
+
else: # len(s) が MAX_LENGTH を超えたので、このsを作ったi_frをfront_indexesから削除
|
|
114
114
|
|
|
115
115
|
front_indexes.pop(0)
|
|
116
116
|
|
1
コード追加
test
CHANGED
|
@@ -47,3 +47,115 @@
|
|
|
47
47
|
|
|
48
48
|
|
|
49
49
|
```
|
|
50
|
+
|
|
51
|
+
|
|
52
|
+
|
|
53
|
+
### 追記
|
|
54
|
+
|
|
55
|
+
|
|
56
|
+
|
|
57
|
+
上記に挙げたコードは、何をやっているかが分かりやすいかもしれませんが、ちょっと芸がない気がしました。それで
|
|
58
|
+
|
|
59
|
+
- one-pass（所与の`body`の最初から最後まで走査するのを一回で済ませること）で、出来ないか？
|
|
60
|
+
|
|
61
|
+
- 無駄を省く何らかの最適化が出来ないか？
|
|
62
|
+
|
|
63
|
+
|
|
64
|
+
|
|
65
|
+
ということで以下のコードになりました。
|
|
66
|
+
|
|
67
|
+
|
|
68
|
+
|
|
69
|
+
```python3
|
|
70
|
+
|
|
71
|
+
# body = 'ABccABcccDEccccDE'
|
|
72
|
+
|
|
73
|
+
body = 'AB123AB67890DExxDEyyyABzzDE##ABDE@@@@@DE' # 動作確認用
|
|
74
|
+
|
|
75
|
+
front = 'AB'
|
|
76
|
+
|
|
77
|
+
rear = 'DE'
|
|
78
|
+
|
|
79
|
+
|
|
80
|
+
|
|
81
|
+
MIN_LENGTH = 2
|
|
82
|
+
|
|
83
|
+
MAX_LENGTH = 10
|
|
84
|
+
|
|
85
|
+
|
|
86
|
+
|
|
87
|
+
result = [] # 条件に該当した文字列を格納するリスト
|
|
88
|
+
|
|
89
|
+
front_indexes = [] # front文字列の開始位置をappendしつつ、使わなくなったものは先頭からpop(0)で削除していくFIFOリスト
|
|
90
|
+
|
|
91
|
+
|
|
92
|
+
|
|
93
|
+
# body を左から読み、front および rear の出現を処理するループ
|
|
94
|
+
|
|
95
|
+
for i in range(len(body)):
|
|
96
|
+
|
|
97
|
+
if body[i:i+len(front)] == front:
|
|
98
|
+
|
|
99
|
+
front_indexes.append(i)
|
|
100
|
+
|
|
101
|
+
elif body[i:i+len(rear)] == rear:
|
|
102
|
+
|
|
103
|
+
for i_fr in [*front_indexes]:
|
|
104
|
+
|
|
105
|
+
s = body[i_fr + len(front):i] # AB と DE の間にある文字列
|
|
106
|
+
|
|
107
|
+
if len(s) <= MAX_LENGTH:
|
|
108
|
+
|
|
109
|
+
if MIN_LENGTH <= len(s):
|
|
110
|
+
|
|
111
|
+
result.append(s)
|
|
112
|
+
|
|
113
|
+
else: # len(s) が MAX_LENGTH を越えていたら、このsを作ったi_frをfront_indexesから削除
|
|
114
|
+
|
|
115
|
+
front_indexes.pop(0)
|
|
116
|
+
|
|
117
|
+
|
|
118
|
+
|
|
119
|
+
|
|
120
|
+
|
|
121
|
+
print(result)
|
|
122
|
+
|
|
123
|
+
print(front_indexes)
|
|
124
|
+
|
|
125
|
+
|
|
126
|
+
|
|
127
|
+
```
|
|
128
|
+
|
|
129
|
+
- サンプル ???? [tera: 369789 別案](https://replit.com/@kilesa/tera-369789-Bie-An?v=1)**@replit**
|
|
130
|
+
|
|
131
|
+
|
|
132
|
+
|
|
133
|
+
**出力結果：**
|
|
134
|
+
|
|
135
|
+
> ['123AB67890', '67890', '67890DExx', 'zz', 'zzDE##AB', 'DE@@@@@']
|
|
136
|
+
|
|
137
|
+
[29]
|
|
138
|
+
|
|
139
|
+
|
|
140
|
+
|
|
141
|
+
|
|
142
|
+
|
|
143
|
+
基本的な流れは以下です。
|
|
144
|
+
|
|
145
|
+
|
|
146
|
+
|
|
147
|
+
- `body` を左端から右端まで読み、`front`文字列が見つかったら、`front_indexes`にその位置を追加します。
|
|
148
|
+
|
|
149
|
+
- `rear`文字列が見つかったら、`front_indexes`に保持している、`front`のインデクスを小さいほうから読み、`front`と`rear`に挟まれている部分文字列を`s` として作ります。
|
|
150
|
+
|
|
151
|
+
- `s` の長さが要件を満たしていれば、該当文字列のリストに追加します。
|
|
152
|
+
|
|
153
|
+
- `s` の長さが要件の最大長を超えていれば、その`s`を作った`front`インデクスは、以後、使われないので、`front_indexes`から削除します。
|
|
154
|
+
|
|
155
|
+
|
|
156
|
+
|
|
157
|
+
上記の実行例では、`front`文字列の出現箇所は、0, 5, 21, 29 の4箇所ですが、プログラムの実行中、`front_indexes`の長さは最大2までにしかならず、プログラム終了時には最後の出現位置の 29 のみを含むリストになっています。
|
|
158
|
+
|
|
159
|
+
|
|
160
|
+
|
|
161
|
+
※いちおう良さげに動いてるっぽいですが、どこかバグっていたら、コメントからお知らせください。
|