Zアルゴリズムは不要ですが、初めて実戦で使ったのでメモ
その文字列がある文字列を何回繰り返してできているのか？の判定が必要です。制約的に愚直に計算できますが、Zアルゴリズムを使って解きました。
題意
- ある文字列s,tが与えられる
- ここで、ある文字列strを考えたときに、別の文字列aをb回繰り返してstrが得られるとき、strはaで割り切れるとする。
- 例えば、abababはab x 3回なので、abで割り切れ、 ababab x 1回なので、abababで割り切れる
- 例えば、abcはabc x 1回でしか割り切れないので、abcでのみ割り切れる
- s,tで割り切れる最小の文字列を答えよ。存在しない場合は-1を出力せよ。
こう考えた
考察は解説に任せます、この問題は文字列のLCM(一般的なものではなく、この問題の範囲の中での言葉です)を求める問題です。
上記例のようにこの問題は、整数の約数のように考えられます。文字札s,tに共通に含まれる共有の約文字列(約数のようなもの)を求め、それぞれの個数のLCMを求めた回数繰り返す。
ポイント：ある文字列の約文字列（約数)の求め方
さて、この動作に必要なのは、以下のような情報を列挙することです。
- abababはab x 3回なので、abで割り切れ、 ababab x 1回なので、abababで割り切れる
- abcはabc x 1回でしか割り切れないので、abcでのみ割り切れる 以下のように考えます。
- あるn文字の文字列の1文字目からi文字目($1\leq i \leq n$)文字目を使って、元の文字列が作れるかを判定する
- この際、nがiで割り切れなければ、その文字列をつなげて作成できるものではないので候補にはならない
-
abababはababをマッチングの方法によっては2回含みますが、この問題の題意では、1回含むなら、abab２回含むならababababになるので、ababからabababを作ることはd系ません
-
- i文字の文字だけで構成される可能性があるなら、元の文字列の1～i文字目, i+1 ～ 2i文字目 , ... , ki+1 ～ n 文字目にその文字が含まれるかを確認する
ここで、Zアルゴリズムを使います。
- iをnまでインクリメントさせながら、1-i文字目までと元の文字列を連結した文字列にZアルゴリズムを適応する
- 得られた配列を元の文字列の1文字目からstep iで回し、i以上であることを確認する
- すべてのforでi以上なら、その文字は1からi文字目までの繰り返しでできている。失敗すれば、1からi文字目までの繰り返しでその文字列を作ることはできない
実装
class zAlgorithm():
def __init__(self, s):
self.sdat = list(map(lambda x: ord(x), s))
self.sl = len(s)
self.res = [0] * self.sl
self.res[0] = self.sl
i, j = 1, 0
while i < self.sl:
while (i+j) < self.sl:
if self.sdat[j] != self.sdat[i+j]:
break
j += 1
self.res[i] = j
if(j == 0):
i += 1
continue
k = 1
while (i+k) < self.sl and (k+self.res[k] < j):
self.res[i+k] = self.res[k]
k += 1
i += k
j -= k
def stringDivisors(s):
z = zAlgorithm(s)
res = dict()
for i in range(len(s) // 2):
curTryLen = i+1
if len(s) % curTryLen != 0:
continue
target = s[:i+1]
t = s[:i+1] + ":" + s
z = zAlgorithm(t)
can = True
for j in range(0, len(s) , curTryLen):
if z.res[len(target) + 1 + j] >= len(target):
continue
can = False
break
if can:
res[target] = len(s) // curTryLen
res[s] = 1
return res
import math
def lcm(x, y):
return (x * y) // math.gcd(x, y)
q = int(input())
for _ in range(q):
s, t = input(), input()
sdiv = stringDivisors(s)
tdiv = stringDivisors(t)
reslen = 0
resval = ""
for k in list(sdiv.keys()):
if k not in tdiv:
continue
tmps = str(k) * lcm(sdiv[k], tdiv[k])
if len(tmps) > reslen:
reslen = len(tmps)
resval = tmps
if resval == "":
print(-1)
else:
print(resval)