C++11: LCS and LIS

C++11: 最長共通部分列(LCS) と 最長増加部分列(LIS) の実装

C++11 の練習のため、Longest Common Subsequence (LCS) と Longest Increasing Subsequence (LIS) を書いてみる。

• Longest common subsequence problem - Wikipedia, the free encyclopedia
• Longest increasing subsequence - Wikipedia, the free encyclopedia

 

C++11 の使い方

最近のコンパイラなら、コンパイルオプション「-std=c++0x」を付けるだけで対応できるはず。

Eclipse CDT なら、プロジェクトの Properties を開き
C/C++ Build -> Settings -> Tool Settings -> お使いのC++コンパイラ -> Miscellaneous -> Other flags
に「-std=c++0x」を追加すればよい。

 

C++11 の主な新機能

概要は下記リンク等を参照。

• C++11のコーディング変更点まとめ | マイナビニュース
• C++11 - Wikipedia

実用性の高そうな機能

• auto: 型推論
• constexpr: コンパイル時定数(および定数式)であることの表現
• range-based for loop: 範囲内を全て走査する for 式
  

  for ( for-range-declaration : expression )

• ラムダ式: 以下の構文で無名の関数オブジェクトをお手軽に書ける
  

  [ lambda-capture ]( parameter-declaration-clause ){ compound-statement }
  

  ちなみに、これは C++11 に限定されないが、いわゆる関数型言語の map, filter, fold(reduce) の機能は
  C++ ではそれぞれ std::transform, std::remove_if, std::accumulate で代替できる。
  (ただし使い勝手は劣る)

• 初期化リスト構文の拡張: std::vector の初期化も簡単にできるようになった。
  
  

  例)

  std::vector<int> v = {1, 2, 3}

 

コード

ideone.com で動かしてみる。

実行結果

Ideone.com - sex6kA - Online C++0x Compiler & Debugging Tool

単純な Dynamic Programming で解いたので、ラムダ式は使いどころが無かった。