Neo-lexicographic Ordering

不念不忘少年蓝@ 2022-09-12 06:59 114阅读 0赞

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : 300 points

--------------------

## Problem Statement ##

Takahashi, who governs the Kingdom of AtCoder, has decided to change the alphabetical order of English lowercase letters.

The new alphabetical order is represented by a string X, which is a permutation of a, b, …, z. The i-th character of X (1≤i≤26) would be the i-th smallest English lowercase letter in the new order.

The kingdom has N citizens, whose names are S1,S2,…,S N  
, where each Si(1≤i≤N) consists of lowercase English letters.  
Sort these names lexicographically according to the alphabetical order decided by Takahashi.

What is the lexicographical order?

--------------------

## Constraints ##

X is a permutation of a, b, …, z.  
2≤N≤50000  
N is an integer.  
1≤∣Si∣≤10 (1≤i≤N)  
Si consists of lowercase English letters. (1≤i≤N)  
Si=Sj (1≤i<j≤N)

--------------------

## Input ##

Input is given from Standard Input in the following format:  
X  
N  
S1  
S2  
⋮  
SN

--------------------

## Output ##

Print N lines. The i-th line (1≤i≤N) should contain the i-th smallest name when the citizens’ names are sorted according to the alphabetical order decided by Takahashi.

--------------------

## Sample Input 1 ##

bacdefghijklmnopqrstuvwxzy
    4
    abx
    bzz
    bzy
    caa

--------------------

## Sample Output 1 ##

bzz
    bzy
    abx
    caa
    In the new alphabetical order set by Takahashi, b is smaller than a and z is smaller than y. Thus, sorting the citizens' names lexicographically would result in bzz, bzy, abx, caa in ascending order.

--------------------

## Sample Input 2 ##

zyxwvutsrqponmlkjihgfedcba
    5
    a
    ab
    abc
    ac
    b

--------------------

## Sample Output 2 ##

b
    a
    ac
    ab
    abc

--------------------

## AC ##

#include <bits/stdc++.h>
    using namespace std;
    #define rep(i, n) for (int i = 0; i < n;i++)
    #define inf 6666666
    int main(){ 
        string x;
        cin >> x;
        int n;
        cin >> n;
        vector<pair<vector<int>, string>> v(n);
        rep(i, n){ 
            string s;
            cin >> s;
            vector<int> tmp(s.size());
            rep(j,s.size()){ 
                rep(k,26){ 
                    if(x[k]==s[j]){ 
                        tmp[j] = k;
                        break;
                    }
                }
            }
            v[i] = make_pair(tmp, s);
        }
        sort(v.begin(), v.end());
        rep(i, n)
                cout<< v[i].second << endl;
    }

--------------------