レーベンシュタイン距離を完全に理解した!(C++編)Zennyapatta📍レーベンシュタイン距離を完全に理解した!(C++編)2021/12/08に公開C++競技プログラミングAtCoderアルゴリズムaojtech※この記事はQiitaからの移行記事ですこんにちは、競プロ絶賛勉強中のyapattaです。JUDGE)のレーベンシュタイン距離の問題を解くことができなかったから、理解するために記事を書いた。プログラミングをやってない人でも理解できる記事を書きたい。この記事を見て、レーベンシュタイン距離について理解して頂ければ幸いである。最後に実装されたコードが書かれているので、コードだけみたい人は是非最後だけ見て欲しい。1)レーベンシュタイン距離(編集距離)とは?レーベンシュタイン距離とは、とりあえず2つの文字列がどのぐらい違っている文字列か表す指標であると理解してもらえるといい。繰り返しすことで、一方の文字列Aをもう一方の文字列Bに変形する。この繰り返しの最小回数をレーベンシュタイン距離という。Judgeある文字列を2つ入力して、その2つの文字列のレーベンシュタイン距離を出力するという問題3)実装方法レーベンシュタイン距離にある、以下の2つの性質を用いて漸化式を立てることで、レーベンシュタイン距離を求められる。y)は文字列xとyのレーベンシュタイン距離を指す。Sになることがわかると思う。具体的に考えてみよう。""(yの長さは0)とする。ここでLP[j][k]はxのj文字目までの文字列と、yのk文字目までの文字列のレーベンシュタイン距離を表す。0;}yapattayapattaです。インフラ、Web、アルゴリズム、コンパイラが好きです。バッジを贈って著者を応援しようバッジを受け取った著者にはZennから現金やAmazonギフトカードが還元されます。バッジを贈るDiscussionyapattayapattaです。インフラ、Web、アルゴリズム、コンパイラが好きです。Proよくある質問LinksX(Twitter)GitHubメディアキットLegal利用規約プライバシーポリシ。