Big Orange Cat's Puzzle

https://acm.cs.nthu.edu.tw/problem/14444/

Big Orange Cat（大橘）喜歡做拼圖。他總共有 n 種類型的謎題，每個謎題 i 都可以用一個字串 Ai 表示，該字串由 ASCII 碼中的所有可見字元組成。

不幸的是，他把謎題搞砸了，真是個巴加諾......現在對於每個拼圖 i，他都找到了一些拼圖塊，由字串 Bi 表示。你的任務是找到一種方法來告訴大橘貓應該從 Bi 的哪些位置取出拼圖塊並重新排列以形成 Ai。

但是，可能有很多可能的方法，而且由於 Big Orange Cat 很懶，請輸出字典順序最小的方法。

重要：比較兩個字串的字典順序的方法如下：從第一個位置（最左側）開始，找到第一個不同的字元。在該位置具有較小字元的字串在字典順序上被視為較小。例如，“abc” < “abd”，因為第一個不同的字母 'c' < 'd'。

輸入

輸入的第一行包含一個整數 n。n 表示拼圖-說明手冊對的數量。

以下 n 行各包含兩個字串 Ai 和 Bi，用空格分隔。它們分別代表第 i 個謎題和說明手冊。

約束

• 1 ≤ n ≤ 500
  1 ≤ n ≤ 500
• 所有字串均由大寫和小寫字母以及任何可由 ASCII 代碼表示的可見符號（ASCII 代碼 33 至 126）組成
• 1 ≤ | 一 |≤ |Bi |≤ 10000 （|S |表示字串 S 的長度 ）

子任務

• 測試案例 1 ~ 2： | 一 |= |Bi |，Ai 和 Bi 中的字元按字典升序排列。
• 測試案例 3 ~ 4： | 一 |= |Bi |
• 測試用例 5 ~ 8：對於每個 Bi，只有一種可能的方法，或者根本沒有方法，來創建相應的 Ai。
• 測試案例 9 ~ 10：沒有額外的限制。

提示：ASCII 碼 33 ~ 126 是： !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~

輸出

輸出 n 行，每行根據情況採用以下兩種格式之一：

1. 如果 Bi 可以形成 Ai ： 輸出 |一i|代表答案的數字遞增 （x1 < x2 < ...），用空格分隔。
2. 輸出 「baganono」 （不帶引號）

請記住在末尾列印 “\n”，不要在每行末尾列印空格 （“ ”）。

提示 1： 找到字典順序上最小的解決方案的關鍵在於 Big Orange Cat 的個性：懶惰。因此，秘訣是取盡可能小的數位。

提示 2： 試著回想一下你是如何確定是否可以在 homework 4 中形成所需的字串的。

第一行是一個整數 n，代表有幾對字串需要處理。在這個例子中，n = 3，表示有 3 組字串需要處理。

接下來的 n 行中，每一行包含兩個字串 A 和 B，用空格分隔：

第一對字串：abc 和 cczbb@aa

第二對字串：aaa 和 aabc

第三對字串：qwe 和 qwe

輸出規則

對於每對字串 A 和 B：

如果可以從字串 B 中選擇字元並重組成字串 A，且可以找出索引序最小的方式，則輸出 B 中的對應索引（從 1 開始計數），這些索引按順序排列。

如果無法從 B 重組出 A，則輸出「baganono」。

第一對字串：

A = abc，B = cczbb@aa

可以從 B 中找到字元 a, b, c，並以字典序最小的方式選擇它們的索引：

'a' 對應 B 中的第 7 個字元（1-based index）

'b' 對應 B 中的第 4 個字元

'c' 對應 B 中的第 1 個字元

因此，輸出 1 4 7。

第二對字串：

A = aaa，B = aabc

在 B 中沒有足夠的 'a' 來重組 A（A 需要 3 個 'a'，但 B 只有 2 個 'a'）。

因此，無法重組，輸出 baganono。

第三對字串：

A = qwe，B = qwe

B 已經是 A 的排列，因此直接按索引順序對應：

'q' 對應 B 的第 1 個字元

'w' 對應 B 的第 2 個字元

'e' 對應 B 的第 3 個字元

因此，輸出 1 2 3。

程式

#include <stdio.h>
#include <string.h>

#define MAX_LEN 10005
#define ASCII_SIZE 128

// 檢查是否可以重組 A 並返回對應的索引數量，若無法重組返回 -1
int can_form(char A[], char B[], int result[]) {
    int countA[ASCII_SIZE] = {0};  // 用來記錄 A 中每個字元的出現次數
    int lenA = strlen(A), lenB = strlen(B);

    // 計算 A 中的字元頻率
    for (int i = 0; i < lenA; i++) {
        countA[(int)A[i]]++;
    }

    int found_count = 0;  // 記錄成功匹配到的字元數量
    int result_index = 0;

    // 遍歷 B，尋找 A 中的字元
    for (int i = 0; i < lenB; i++) {
        if (countA[(int)B[i]] > 0) {
            result[result_index++] = i;  // 將匹配的 B 中索引記錄下來
            countA[(int)B[i]]--;  // 已匹配，減少該字元次數
            found_count++;
        }
        if (found_count == lenA) break;  // 如果已找到所有字元則提前結束
    }

    if (found_count != lenA) return -1;  // 若字元不完全匹配，返回 -1
    return result_index;  // 返回找到的字元數量
}

int main() {
    int n;
    scanf("%d", &n);  // 讀取測試案例數量

    char A[MAX_LEN], B[MAX_LEN];
    int result[MAX_LEN];  // 存放 B 中對應的索引結果

    for (int i = 0; i < n; i++) {
        scanf("%s %s", A, B);  // 讀取 Ai 和 Bi

        int result_len = can_form(A, B, result);  // 檢查是否可以重組

        if (result_len == -1) {
            printf("baganono\n");  // 無法重組
        } else {
            for (int j = 0; j < result_len; j++) {
                printf("%d", result[j] + 1);  // 輸出 1-based index
                if (j != result_len - 1) {
                    printf(" ");
                } else {
                    printf("\n");
                }
            }
        }
    }

    return 0;
}