PukiWiki/1.4 ※しろくろのへや:do_diffから移動してきました。 -- ぱんだ 差分表示の改造† 文書比較アルゴリズムより... 文書比較を行う問題は、2つの文書A,Bの最長共通部分(LCS Longuest Common Subsequence)、または最小エディット距離(SED Shotest Edit Distance)を求める問題と等価である。 …だそうです。なんとなく速そうだったので、PukiWikiの差分表示ルーチンをO(NP)アルゴリズムで作ってみようと思った次第で。 http://www.cs.arizona.edu/people/gene [1] E.W.Myers, "An O(ND) difference algorithm and its variations", Algorithmixa, 1 (1986), pp.251-266 [2] S.W.