Sequence/Levenshtein_Distance.py

View this file on GitHub
Last update: 2022-11-26 03:55:08+09:00

Code

#レーベンシュタイン距離
def Levenshtein_Distance(S, T):
    """ S,T におけるレーベンシュタイン距離 (編集距離) を求める.

    """

    M=len(S); N=len(T)
    DP=[[0]*(N+1) for _ in range(M+1)]

    for i in range(1,M+1):
        D=DP[i]
        E=DP[i-1]
        for j in range(1,N+1):
            if S[i-1]==T[j-1]:
                D[j]=min(D[j-1]+1, E[j]+1, E[j-1])
            else:
                D[j]=min(D[j-1], E[j], E[j-1])+1

    return D[-1]

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