クローン・類似性

C0. 与えられたソースファイルを字句解析せよ．

C1. 与えられたファイル対がType-1クローンであるか判定せよ．

空白やタブ等のコーディングスタイルを除くと一致するプログラム対をType-1クローンという．字句列の一致とみなしてよい．

C2. ソースプログラムから得られた字句のうち，変数名を特殊シンボル`V`，リテラルを特殊シンボル`L`に置換して出力せよ．これを用いて，与えられたファイル対がType-2クローンか判定せよ．

Type-1に加え，変数名やリテラル等の字句単位での違いを除くと一致するソースプログラム対をType-2クローンという．

C3. 与えられた2つの文字列の最長共通部分列 (longest common subsequence; LCS) を求めよ．

C4. 与えられた2つのソースプログラムの行差分（diff）を求めよ．

ここでdiffは，ソースプログラムを行の並び（列）とみなしたうえで，最長共通部分列に含まれなかった行を追加・削除された行とみなす．

C5. 文脈長2として，hunkの列としてdiffを出力せよ（`diff -u -c2`を模倣せよ）．

C6. 与えられたファイル対がType-3クローンを含むか判定せよ．

Type-3クローンは，Type-2に加え，字句単位よりも大きな違いを含むものを許容する．

（この問題が曖昧でつらそう．もう少し限定してあげたい．）

C7. Type-1クローン関係を含むような同値関係をなす，ソースプログラム$s$からのハッシュ関数$h(s)$を設計せよ．

これを用いて，（大きめの例題）からすべてのType-1クローン関係を特定せよ．

C8. コード片に対するメトリクス値に基づくベクトル空間を構成し，ベクトルの類似性に基づきクローンを検出せよ．