大神的世界

想法

1. 每給一個條件就轉換一次 （ O( n*m ) ) 一定 TLE 沒什好試的

2. 建立轉換表，再一次全部轉換  （ 建立轉換表 (  O(m) )  ;  全部轉換 ( O(n) ) ;  所以時間複雜度為 O(m)  （因為最終測資的 m 比較大) )

因此選用第 2 步

步驟

0. 編碼  ( 定義 a 從 1 開始擺放 ， A 從 27 開始， 0 從 53 開始 )

1. 利用 symbol 紀錄轉換結果 ， 初始值為 symbol [ i ] = i   i = 1, 2, 3, ....

2. 將 str 、 sym1 和 sym2 編碼

3. 更新 symbol ( linear scan 找尋 symbol [ i ] = sym1 [ j ]  ， 將 symbol [ i ] 轉成 sym2 [ j ] )

4. 轉換 str  ( 利用 symbol )

5. 將 str 解碼 

#include <iostream>

using namespace std;

#define Max_m 200000
#define Max_n 10000001

char str[Max_m];
char sym1[Max_n], sym2[Max_n];

int main()
{
    char symbol[63];
    int n, m;

    char *ptr1, *ptr2, *ptr3;
    int i;

    while(cin >> n >> m){
        cin >> str;
        cin >> sym1 >> sym2;

        for(i = 1, ptr1 = symbol+1; ptr1 != symbol+63; ptr1++)
            *ptr1 = i++;

        for(ptr1 = str; *ptr1; ptr1++)
            if(*ptr1 >= 'a')
                *ptr1 -= 96;  // 0x61 - 1
            else if(*ptr1 >= 'A')
                *ptr1 -= 38;  // 0x41 - 26 - 1
            else
                *ptr1 += 5;  // 0x30 - 52 - 1

        for(ptr1 = sym1; *ptr1; ptr1++)
            if(*ptr1 >= 'a')
                *ptr1 -= 96;  // 0x61 - 1
            else if(*ptr1 >= 'A')
                *ptr1 -= 38;  // 0x41 - 26 - 1
            else
                *ptr1 += 5;  // 0x30 - 52 - 1

        for(ptr1 = sym2; *ptr1; ptr1++)
            if(*ptr1 >= 'a')
                *ptr1 -= 96;  // 0x61 - 1
            else if(*ptr1 >= 'A')
                *ptr1 -= 38;  // 0x41 - 26 - 1
            else
                *ptr1 += 5;  // 0x30 - 52 - 1

        for(ptr1 = sym1, ptr2 = sym2; *ptr1; ptr1++, ptr2++)
            for(ptr3 = symbol; ptr3 != symbol + 63; ptr3++)
                if(*ptr3 == *ptr1)
                    *ptr3 = *ptr2;

        for(ptr1 = str; *ptr1; ptr1++)
            *ptr1 = *(symbol + *ptr1);

        for(ptr1 = str; *ptr1; ptr1++)
            if(*ptr1 <= 26)
                *ptr1 += 96;  // 0x61 - 1
            else if(*ptr1 <= 52)
                *ptr1 += 38;  // 0x41 - 26 - 1
            else
                *ptr1 -= 5;  // 0x30 - 52 - 1

        cout << str << endl;
    }

    return 0;
}