#1177115 (PyPy3) No.3626 Not a Prefix

• 問題: No.3626 Not a Prefix
• ユーザー: 回転
• 提出日時: 2026-08-14 23:38:46
• 言語: PyPy3 (7.3.17)
• 結果: TLE
• 実行時間: -
• コード長: 3,888 bytes
• コンパイル時間: 231 ms
• コンパイル使用メモリ: 95,852 KB
• 実行使用メモリ: 771,612 KB
• 最終ジャッジ日時: 2026-08-14 23:39:02
• 合計ジャッジ時間: 16,665 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

ファイルパターン	結果
sample	AC * 2
other	AC * 43 TLE * 2

ソースコード

import pypyjit
pypyjit.set_param("max_unroll_recursion=-1")
import sys
sys.setrecursionlimit(5 * 10**5 + 100)
import random

MOD = (1 << 61) - 1
BASE = random.randrange(1 << 20, MOD - 1)

POW = [1]


class RollingHash:
    __slots__ = ("hash_arr",)

    @staticmethod
    def reserve(n: int):
        """BASE^0 ... BASE^n を事前計算する"""
        p = POW
        if len(p) > n:
            return

        base = BASE
        mod = MOD
        x = p[-1]
        append = p.append

        for _ in range(n + 1 - len(p)):
            x = x * base % mod
            append(x)

    def __init__(self, S: str = ""):
        n = len(S)

        if len(POW) <= n:
            RollingHash.reserve(n)

        # hash_arr[i] = hash(S[:i])
        arr = [0] * (n + 1)

        base = BASE
        mod = MOD
        h = 0

        for i, c in enumerate(S, 1):
            h = (h * base + ord(c)) % mod
            arr[i] = h

        self.hash_arr = arr

    def append(self, c: str):
        """末尾に1文字追加"""
        arr = self.hash_arr

        h = (arr[-1] * BASE + ord(c)) % MOD
        arr.append(h)

        # get() のための累乗も必要なら伸ばす
        if len(POW) < len(arr):
            POW.append(POW[-1] * BASE % MOD)

    def pop(self):
        """末尾1文字削除"""
        arr = self.hash_arr

        if len(arr) == 1:
            raise IndexError("pop from empty RollingHash")

        arr.pop()

    def get(self, l: int, r: int) -> int:
        """hash(S[l:r])"""
        arr = self.hash_arr

        # これがかなり重要
        # prefixなら掛け算すら不要
        if l == 0:
            return arr[r]

        ret = arr[r] - arr[l] * POW[r - l] % MOD

        if ret < 0:
            ret += MOD

        return ret

    def __len__(self):
        return len(self.hash_arr) - 1

class RConst:
    Mask30 = (1 << 30) - 1
    Mask31 = (1 << 31) - 1
    Mod = (1 << 61) - 1
    cf = 0
    rui_cf = [1]

    @staticmethod
    def calc_mod(x: int) -> int:
        xu, xd = x >> 61, x & RConst.Mod
        ret = xu + xd
        if RConst.Mod <= ret:
            ret -= RConst.Mod
        return ret

    @staticmethod
    def sub(a: int, b: int) -> int:
        if a < b:
            return a + RConst.Mod - b
        return a - b

    @staticmethod
    def mul(a: int, b: int) -> int:
        au, ad = a >> 31, a & RConst.Mask31
        bu, bd = b >> 31, b & RConst.Mask31
        mid = ad * bu + au * bd
        midu, midd = mid >> 30, mid & RConst.Mask30
        return RConst.calc_mod(((au * bu) << 1) + midu + (midd << 31) + ad * bd)

    @staticmethod
    def make_rui_cf(x: int):
        l = len(RConst.rui_cf)
        for _ in range(x - l + 1):
            RConst.rui_cf.append(RConst.mul(RConst.cf, RConst.rui_cf[-1]))

from collections import defaultdict
input = sys.stdin.readline
def main():
    N,M = list(map(int,input().split()))
    S = [input().strip() for _ in range(N)]

    d = defaultdict(int)
    end = defaultdict(int)
    for i in range(N):
        rh = RollingHash(S[i])
        for j in range(len(S[i])):
            d[rh.get(0,j+1)] += 1
        end[rh.get(0,len(S[i]))] += 1

    ans = []
    end_count = 0
    now_RH = RollingHash("")
    def f():
        nonlocal end_count
        for i in range(26):
            if(end_count >= N - M + 1):return
            c = chr(ord("a") + i)
            now_RH.append(c)
            hash = now_RH.get(0,len(ans)+1)
            end_count += end[hash]

            if(end_count < N - M + 1):
                if(d[hash] + end_count - end[hash] >= N - M + 1):
                    ans.append(c)
                    f()
                    ans.pop()
                else:
                    print("Yes")
                    print("".join(ans + [c]))
                    exit()

            end_count -= end[hash]
            now_RH.pop()

    f()
    print("No")

main()