2010-01-19から1日間の記事一覧

最長共通部分文字列と最長共通部分列

今日から少し、典型DPを扱ってみようと思う。最長共通部分文字列(longest common substring)と最長共通部分列(longest common subsequence)。前者は連続という条件つきで、後者は連続でなくても順序が維持されていればよいというもの。 前者はO( (n+m)min(n,…