Problem:


Score : 1100 points

Problem Statement

We will call a string that can be obtained by concatenating two equal strings an even string.
For example, xyzxyz and aaaaaa are even, while ababab and xyzxy are not.

For a non-empty string S, we will define f(S) as the shortest even string that can be obtained by appending one or more characters to the end of S.
For example, f(abaaba)=abaababaab.
It can be shown that f(S) is uniquely determined for a non-empty string S.

You are given an even string S consisting of lowercase English letters.
For each letter in the lowercase English alphabet, find the number of its occurrences from the l-th character through the r-th character of f^{10^{100}} (S).

Here, f^{10^{100}} (S) is the string f(f(f( ... f(S) ... ))) obtained by applying f to S 10^{100} times.

Constraints

2 \leq |S| \leq 2\times 10^5

1 \leq l \leq r \leq 10^{18}

S is an even string consisting of lowercase English letters.

l and r are integers.

Input

Input is given from Standard Input in the following format:

S
l r

Output

Print 26 integers in a line with spaces in between.
The i-th integer should be the number of the occurrences of the i-th letter in the lowercase English alphabet from the l-th character through the r-th character of f^{10^{100}} (S).

Sample Input 1

abaaba
6 10

Sample Output 1

3 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Since f(abaaba)=abaababaab, the first ten characters in f^{10^{100}}(S) is also abaababaab. Thus, the sixth through the tenth characters are abaab. In this string, a appears three times, b appears twice and no other letters appear, and thus the output should be 3 and 2 followed by twenty-four 0s.

Sample Input 2

xx
1 1000000000000000000

Sample Output 2

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1000000000000000000 0 0

Sample Input 3

vgxgpuamkvgxgvgxgpuamkvgxg
1 1000000000000000000

Sample Output 3

87167725689669676 0 0 0 0 0 282080685775825810 0 0 0 87167725689669676 0 87167725689669676 0 0 87167725689669676 0 0 0 0 87167725689669676 141040342887912905 0 141040342887912905 0 0



Sample input:
abaaba
6 10


Sample output:
3 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import Counter

"""
・実験すると、何回かやるとFibonacci（未証明）
"""

S = readline().rstrip()
l,r = map(int,read().split())

def double_naive(S):
    L = len(S)
    for i in range(1,L+1):
        T = S[:i] * 2
        if len(T) > L and T[:L] == S:
            return T

def Z_algorithm(S):
    # 共通接頭辞の長さを返す
    N=len(S)
    arr = [0]*N
    arr[0] = N
    i,j = 1,0
    while i<N:
        while i+j<N and S[j]==S[i+j]:
            j += 1
        arr[i]=j
        if not j:
            i += 1
            continue
        k = 1
        while i+k<N and k+arr[k]<j:
            arr[i+k] = arr[k]
            k += 1
        i += k; j -= k
    return arr

def F(S):
    N = len(S)
    opt_len = N
    Z = Z_algorithm(S)
    for x in range(N//2+1,N):
        z = Z[x]
        if x + z >= N:
            opt_len = x
            break
    return S[:opt_len] * 2

S = F(S)
S = F(S)
T = F(S)

# S,T,TS,TST,...

L = [len(S), len(T)]
for _ in range(100):
    L.append(L[-1] + L[-2])
ctr = [Counter(S), Counter(T)]
for _ in range(100):
    ctr.append(ctr[-1] + ctr[-2])

def get_dist(N,R):
    # S_NにおけるR番目以下
    if N == 0:
        return Counter(S[:R])
    if N == 1:
        return Counter(T[:R])
    if L[N-1] >= R:
        return get_dist(N-1,R)
    return ctr[N-1] + get_dist(N-2,R-L[N-1])

ctr = get_dist(99,r) - get_dist(99,l-1)

answer = [ctr[x + ord('a')] for x in range(26)]
print(*answer)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import Counter

"""
・実験すると、何回かやるとFibonacci（未証明）
"""

S = readline().rstrip()
l,r = map(int,read().split())

def double_naive(S):
    L = len(S)
    for i in range(1,L+1):
        T = S[:i] * 2
        if len(T) > L and T[:L] == S:
            return T

def Z_algorithm(S):
    # 共通接頭辞の長さを返す
    N=len(S)
    arr = [0]*N
    arr[0] = N
    i,j = 1,0
    while i<N:
        while i+j<N and S[j]==S[i+j]:
            j += 1
        arr[i]=j
        if not j:
            i += 1
            continue
        k = 1
        while i+k<N and k+arr[k]<j:
            arr[i+k] = arr[k]
            k += 1
        i += k; j -= k
    return arr

def F(S):
    N = len(S)
    opt_len = N
    Z = Z_algorithm(S)
    for x in range(N//2+1,N):
        z = Z[x]
        if x + z >= N:
            opt_len = x
            break
    return S[:opt_len] * 2

S = F(S)
T = F(S)

# S,T,TS,TST,...

L = [len(S), len(T)]
for _ in range(100):
    L.append(L[-1] + L[-2])
ctr = [Counter(S), Counter(T)]
for _ in range(100):
    ctr.append(ctr[-1] + ctr[-2])

def get_dist(N,R):
    # S_NにおけるR番目以下
    if N == 0:
        return Counter(S[:R])
    if N == 1:
        return Counter(T[:R])
    if L[N-1] >= R:
        return get_dist(N-1,R)
    return ctr[N-1] + get_dist(N-2,R-L[N-1])

ctr = get_dist(99,r) - get_dist(99,l-1)

answer = [ctr[x + ord('a')] for x in range(26)]
print(*answer)

Submission status: Wrong Answer

Solution code:
def getSS(S):
    helfLength = int(len(S) / 2) + 1
    
    while S[:int(len(S[helfLength:]))] != S[helfLength:]:
        helfLength += 1
        
    return S[:helfLength] * 2

result = ""
S = input()
SS = S
lr = [int(i) for i in input().split()]

i = 0
while i < 10:
    SS = getSS(SS)
    i += 1

cList = [chr(i) for i in range(97, 97+26)]

for c in cList:
    result += str(SS[lr[0]-1:lr[1]].count(c)) + " "

print(result.rstrip())

Submission status: Wrong Answer

Solution code:
S = input()

helfLength = int(len(S) / 2) + 1

while S[:int(len(S[helfLength:]))] != S[helfLength:]:
    helfLength += 1

print(helfLength * 2)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

S = readline().rstrip()
l,r = map(int,read().split())

def double_naive(S):
    L = len(S)
    for i in range(1,L+1):
        T = S[:i] * 2
        if len(T) > L and T[:L] == S:
            return T

def Z_algorithm(S):
    # 共通接頭辞の長さを返す
    N=len(S)
    arr = [0]*N
    arr[0] = N
    i,j = 1,0
    while i<N:
        while i+j<N and S[j]==S[i+j]:
            j += 1
        arr[i]=j
        if not j:
            i += 1
            continue
        k = 1
        while i+k<N and k+arr[k]<j:
            arr[i+k] = arr[k]
            k += 1
        i += k; j -= k
    return arr

def F(S):
    N = len(S)
    opt_len = N
    Z = Z_algorithm(S)
    for x in range(N//2+1,N):
        z = Z[x]
        if x + z >= N:
            opt_len = x
            break
    return S[:opt_len] * 2

S = F(S)
S = F(S)
T = F(S)
S = S[:len(S)//2]
T = T[:len(T)//2]

S = np.array(list(S)) - ord('a')
T = np.array(list(T)) - ord('a')

# S,T,TS,TST,...

L = [len(S), len(T)]
for _ in range(100):
    L.append(L[-1] + L[-2])
ctr = [np.bincount(S,minlength=26), np.bincount(T,minlength=26)]
for _ in range(100):
    ctr.append(ctr[-1] + ctr[-2])

def get_dist(N,R):
    # S_NにおけるR番目以下
    if N == 0:
        return np.bincount(S[:R],minlength=26)
    if N == 1:
        return np.bincount(T[:R],minlength=26)
    if L[N-1] >= R:
        return get_dist(N-1,R)
    return ctr[N-1] + get_dist(N-2,R-L[N-1])

c = get_dist(99,r) - get_dist(99,l-1)

print(*c)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3


M = 10 ** 9 + 7
a = ord('a')


def check_cycle(t, p):

    len_t = len(t)
    if len_t % p != 0:
        return False
    pre = t[: p]
    for i in range(p, len_t, p):
        if t[i: i + p] != pre:
            return False

    return True


def solve_cycle(t, l, r):

    len_t = len(t)
    ql = (l - 1) // len_t
    rl = (l - 1) % len_t
    qr = r // len_t
    rr = r % len_t

    ans = [0] * 26
    for ch in t:
        ans[ord(ch) - a] += 1
    for j in range(26):
        ans[j] *= (qr - ql)
    for ch in t[: rr + 1]:
        ans[ord(ch) - a] += 1
    for ch in t[: rl + 1]:
        ans[ord(ch) - a] -= 1

    return ans


def calc_part(tp, tm, len_p, len_m, dp0, dp1, r, ir):

    num_p = 0
    num_m = 0
    for i in range(ir, -1, -1):
        n = dp0[i] * len_p + dp1[i] * len_m
        if n <= r:
            num_p += dp0[i]
            num_m += dp1[i]
            r -= n

    vec = [0] * 26
    tr = tp
    if len_p + len_m < r:
        num_p += 1
        num_m += 1
        r -= len_p + len_m
    elif len_p < r:
        num_p += 1
        r -= len_p
        tr = tm
    for ch in tp:
        vec[ord(ch) - a] += num_p
    for ch in tm:
        vec[ord(ch) - a] += num_m
    for ch in tr[: r]:
        vec[ord(ch) - a] += 1

    return vec


def solve_part(t, len_p, l, r):

    len_t = len(t)
    len_m = len_t - 2 * len_p
    dp0 = [0] * 121
    dp1 = [0] * 121
    dp0[0] = 2
    dp1[0] = 1

    for i in range(1, 121):
        dp0[i] = dp0[i - 1] + dp1[i - 1]
        dp1[i] = dp0[i - 1]
        n = dp0[i] * len_p + dp1[i] * len_m
        if l - 1 <= n:
            il = i - 1
        if r <= n:
            ir = i - 1
            break

    vec_l = calc_part(t[: len_p], t[len_p: len_p + len_m], len_p, len_m, dp0, dp1, l - 1, il)
    vec_r = calc_part(t[: len_p], t[len_p: len_p + len_m], len_p, len_m, dp0, dp1, r, ir)

    ans = [vec_r[j] - vec_l[j] for j in range(26)]

    return ans


def solve(s, l, r):

    t = s[: len(s) // 2]
    len_t = len(t)
    if len_t == 1:
        return solve_cycle(t, l, r)

    len_p = 0
    ph = 0
    sh = 0
    base = 1
    for i in range(len_t // 2):
        ph *= 26
        ph += ord(s[i]) - a
        ph %= M
        sh += base * (ord(s[-1 - i]) - a)
        sh %= M
        if ph == sh:
            if check_cycle(t, i + 1):
                return sovle_cycle(t[: i + 1], l, r)
            elif t[: i + 1] == t[-1 - i:]:
                len_p = i + 1
        base *= 26

    if len_p == 0:
        return solve_cycle(t, l, r)

    return solve_part(t, len_p, l, r)


def main():
    s = input()
    l, r = input().split()
    l = int(l)
    r = int(r)

    print(' '.join(list(map(str, solve(s, l, r)))))


if __name__ == '__main__':
    main()