結果

問題 No.2858 Make a Palindrome
ユーザー prd_xxx
提出日時 2024-08-25 16:23:41
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,177 bytes
コンパイル時間 356 ms
コンパイル使用メモリ 82,504 KB
実行使用メモリ 137,188 KB
最終ジャッジ日時 2024-08-25 16:23:54
合計ジャッジ時間 11,758 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16 WA * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

def manacher(_S):
    L = 2*len(_S)+1
    radius = [0]* L
    S = ['#'] * L
    for i in range(len(_S)):
        S[2*i+1] = _S[i]
    i = j = 0
    while i < L:
        while i-j >= 0 and i+j < L and S[i-j] == S[i+j]:
            j += 1
        radius[i] = j
        k = 1
        while i-k >= 0 and i+k < L and k+radius[i-k] < j:
            radius[i+k] = radius[i-k]
            k += 1
        i += k
        j -= k
    return radius

def solve(N,M,S):
    m1 = manacher(S)
    for i,m in enumerate(m1):
        if i%2 == 0:
            l = m - 1
        else:
            l = (m//2)*2 - 1
        if l >= M: return 1
    m2 = manacher(S+S)
    for i,m in enumerate(m2):
        if i%2 == 0:
            l = m - 1
        else:
            l = (m//2)*2 - 1
        if l >= M: return 2
    m3 = manacher(S+S+S)
    maxl = 0
    for i,m in enumerate(m3):
        if i%2 == 0:
            l = m - 1
        else:
            l = (m//2)*2 - 1
        if l >= M: return 3
        maxl = max(maxl,l)
    if maxl >= N:
        return 0--M//N
    else:
        return -1

T = int(input())
for _ in range(T):
    N,M = map(int,input().split())
    S = input()
    print(solve(N,M,S))
0