SRM148 DIV2 600(置換の問題)

The keycaps on a keyboard have been switched around, and the user is now trying to remember what he was trying to type.
Create a class CeyKaps containing the method decipher that takes a string typed, representing the visible message on the screen, and a vector switched, representing the keycap switches. The method should return the original intended message (what keys the user thought he was pressing).
A keycap can be switched around more than once. For example, if someone switched around 'A' and 'S', then switched around 'S' and 'D', then 'D' would be where 'A' originally was, 'S' where 'D' was, and 'A' where 'S' was.
The elements of switches will be formatted as (quotes added for clarity) "*:*", where the *'s represent the keycaps to be switched. The above example would be represented as: {"A:S","S:D","D:A"}, or alternately as {"S:A","D:S","A:D"} or any other such combination. The order of the keycaps doesn't matter, but the order of the switches does.

と言う問題。文字列の長さをN、置換の数をMとするとO(N + M)で処理する方法を思いついたのでメモ。

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

class CeyKaps {
public:
    string decipher(string typed, vector<string> switches) {
        string::value_type a[26 + 'A'], b[26 + 'A'];
        for (int i = 'A'; i <= 'Z'; i++) a[i] = b[i] = i;
        for (int i = 0; i < switches.size(); i++) {
            swap(a[b[switches[i][0]]], a[b[switches[i][2]]]);
            swap(b[switches[i][0]], b[switches[i][2]]);
        }
        
        string d;
        for (int i = 0; i < typed.length(); i++) d += a[typed[i]];
        return d;
    }
};

// a[文字] = 置換後の文字
// b[文字] = aの中で文字がある位置

置換が沢山与えられたときはこうやって解くと良いんじゃないかと思った。