二種類の方針を紹介します。

方針 1. 比較関数を実装する

文字列の辞書順が変わってしまっているため、\(S_1, S_2, \dots, S_N\) をソートするにあたって、標準のソート関数を用いることはできません。そこで、文字列を比較する関数を定義し、それをソート関数に渡すことで問題文の指示通りに並べ替えることができます。

与えられた \(X\) を用いて、各英小文字に対し、それが何番目に小さいか表す配列を用意することで、比較を \(O(\max |S_i|)\) で行うことができます。

実装例 (C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
    string X;
    cin >> X;
    vector<int> pos(26);
    for (int i = 0; i < 26; ++i) {
        pos[X[i] - 'a'] = i;
    }
    int N;
    cin >> N;
    vector<string> S(N);
    for (string& s : S) {
        cin >> s;
    }
    sort(begin(S), end(S), [&](const string& s, const string& t) {
        // 文字列の比較
        int len = min(size(s), size(t));
        for (int i = 0; i < len; ++i) {
            if (s[i] != t[i]) {
                return pos[s[i] - 'a'] < pos[t[i] - 'a'];  
            }
        }
        return size(s) < size(t);
    });
    for (const string& s : S) {
        cout << s << '\n';
    }
}

方針 2. 別の数列に置き換えてからソートを行う

多くの言語において、文字列や配列が格納された配列をソートするとき、辞書順に基づく比較を行います。そのため、全ての文字をその文字が \(X\) において何番目に登場するか表す数値に変換したのち、標準の関数を用いてソートを行い、\(X\) を用いて数値を文字に戻すという処理を行うことでこの問題を解くことができます。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    string X;
    cin >> X;
    vector<int> pos(26);
    for (int i = 0; i < 26; ++i) {
        pos[X[i] - 'a'] = i;
    }
    int N;
    cin >> N;
    vector<vector<int>> S(N);
    for (vector<int>& v : S) {
        string s;
        cin >> s;
        for (const char c : s) {
            v.push_back(pos[c - 'a']);
        }
    }
    sort(begin(S), end(S));
    for (const vector<int>& s : S) {
        for (const int x : s) {
            cout << X[x];
        }
        cout << '\n';
    }
    return 0;
}