String/Substring_Count.py

• View this file on GitHub
• Last update: 2022-12-24 17:50:01+09:00

Code

def Substring_Count(S, Mod=None):
    """ 文字列 S の異なる連続とは限らない部分列の個数を求める.

    Mod: 余り
    """

    #前処理
    N=len(S)
    A=list(set(S))
    inv_A={A[i]:i for i in range(len(A))}

    B=[[N]*len(A) for _ in range(N+1)]

    for i in range(N-1,-1,-1):
        Bi=B[i]; Bii=B[i+1]
        for j in range(len(A)):
            Bi[j]=Bii[j]
        Bi[inv_A[S[i]]]=i

    #DP部
    DP=[0]*(N+1)
    if Mod==None:
        DP[0]=1
    else:
        DP[0]=1%Mod

    for i in range(N):
        Bi=B[i]
        for j in range(len(A)):
            if Bi[j]>=N:
                continue

            DP[B[i][j]+1]+=DP[i]
            if Mod!=None:
                DP[B[i][j]+1]%=Mod
    #集計
    if Mod==None:
        return sum(DP)
    else:
        return sum(DP)%Mod

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page