[UVA] 179 Code Breaking

思路：這個目題有兩部份，一部份是求k，即encode的period。另一部份是求encode的permutation。
我求k的作法比較暴力，即從 k = 1開始，試到 k = n (n為cypher字串長，而非plain text長度)。如果中間遇到可以用的permutation，就可以結束迴圈作decode了。其中又可以發現，k必為 n 的因數 (n % k == 0)，所以可以跳過不可能的k值。

求permutation就比較講究。最直接的作法是做 k 窮舉，即 1234, 1243, .... 4321然後一一驗證。不過經由上次facebook hackercup 的教訓後，我發現這種匹配的問題，只要能將plain text與cypher的關係建構成二分圖，都可以用Bipartie match來解。只要能找到完全匹配，即為合格的permutation。建構二分圖的步驟如下：
1. 把plain text (P) 與 cypher (C) 每 k 個字元切一個chunk。cypher一定會沒有餘數，而plain text呢？只要在後面補?即可。如:  k = 3, plain text = abcd  --->  abc, d??。補問號可以讓P 與 C 的長度相同，把matching的邏輯簡化，也不失一般性，算是實作的一個trick。

2. 對 P 與 C 的第一個chunk，每個相同的 P[i] 與 C[j] 建一條邊，代表它們有潛力被匹配。於是我們得到左右兩邊各為 k 個 vertex的二分圖，而其上的邊代表相同字位交換位置的可能性。如果P或C有vertex沒被邊連到，那代表無法完全匹配，即此 k 不可行。

3. 對 P 和 C 之後的chunk，一次處理一個chunk。讓offset 代表 目前這個chunk離字串首的位移，對每個不同的P[offset + i] 與 C[offset + j]，如果之前有邊的話 (因為前幾個chunk該位置都可以match) , 便把邊移掉，不然無視。這一步是確保在每個chunk 中，P_chunk的第i 個字元 都可以匹配到 C_chunk的第j 字元。注意，我們的二分圖一直都是 兩個各有k點。


void BuildGraph(string text, string cypher, int k, vector< set<int> >&graph) {
   graph.clear();
   // Add edges
   for (int i = 0; i < k; ++i) {
      set<int> edges;
      for (int j = 0; j < k; ++j) {
         if (text[i] == cypher[j])
            edges.insert(j);
      }
      graph.push_back(edges);
   }

   // Remove invalid edges
   int len = text.length();
   for (int start = k; start < len; start += k) {
      for (int i = start; i < start + k; ++i) {
         int gi = i - start;
         for (int j = start; j < start + k; ++j) {
            int gj = j - start;
            if (text[i] != cypher[j]) {
               if (graph[gi].find(gj) != graph[gi].end()) {
                  graph[gi].erase(gj);
               }
            }
         }
      }
   }
}



最後把二分圖丟到Bipartie matching。完全匹配即為合格的k。permutation即為匹配。

有用的測資：

Input:
------
aaaaabbbbbcccccdddddeeeeefffff
aaaabacbbbcbddccdceeededfffeff
1234567890

aaaabbccuvwxuvwx
aaaaccbbxwuvxwuv
ABCD
#

OUTPUT:
-------
4632150?987?
CDBA