解题思路

• 本题要求：给定整数数组 a 与若干字符串 s，判断 s 能否与 a 建立一一对应(双射) 的位置映射：相同数字对应相同字符，且相同字符对应相同数字，并且长度相等。

• 核心做法：把序列按首次出现顺序压缩成模式串。

  • 对数组 a：从左到右，第一次见到某个值就分配一个新的编号 0,1,2,...，形成模式序列 patA。
  • 对任意待判字符串 s：同样按字符的首次出现分配编号，得到 patS。
  • 若 |s| != n 直接否；否则比较 patS 与 patA 是否完全相同，相同则存在双射，对应输出 YES，否则 NO。

• 该方法天然保证了“双向一致”：

  • 相同数字得到相同编号 ⇒ 必有相同字符；
  • 相同字符得到相同编号 ⇒ 必有相同数字； 两个模式完全一致即等价于存在一一映射。

复杂度分析

• 预处理数组 a 生成 patA：O(n)。
• 对每个字符串 s 生成 patS 并比较：O(|s|)。
• 若所有测试中 Σn 与 Σ|s| 不超过 2e5（题面给定），总时间 O(Σn + Σ|s|)，空间 O(n + |s|max)，满足要求。

代码实现

Python

import sys

# 将序列按首次出现顺序映射成模式编号序列
def build_pattern_from_array(arr):
    mp = {}                     # 值 -> 首次出现编号
    nxt = 0
    pat = []
    for v in arr:
        if v not in mp:
            mp[v] = nxt
            nxt += 1
        pat.append(mp[v])
    return pat

def build_pattern_from_string(s):
    mp = {}                     # 字符 -> 首次出现编号
    nxt = 0
    pat = []
    for ch in s:
        if ch not in mp:
            mp[ch] = nxt
            nxt += 1
        pat.append(mp[ch])
    return pat

def main():
    data = sys.stdin.read().strip().split()
    it = iter(data)
    t = int(next(it))
    out = []
    for _ in range(t):
        n = int(next(it))
        arr = [int(next(it)) for _ in range(n)]
        base = build_pattern_from_array(arr)
        m = int(next(it))
        for _ in range(m):
            s = next(it)
            if len(s) != n:
                out.append("NO")
            else:
                out.append("YES" if build_pattern_from_string(s) == base else "NO")
    print("\n".join(out))

if __name__ == "__main__":
    main()

Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;

public class Main {

    // 将整型数组按首次出现顺序压缩为模式
    static int[] patternFromArray(int[] a) {
        Map<Integer, Integer> mp = new HashMap<>();
        int n = a.length, nxt = 0;
        int[] pat = new int[n];
        for (int i = 0; i < n; i++) {
            Integer v = a[i];
            if (!mp.containsKey(v)) mp.put(v, nxt++);
            pat[i] = mp.get(v);
        }
        return pat;
    }

    // 将字符串按首次出现顺序压缩为模式
    static int[] patternFromString(String s) {
        Map<Character, Integer> mp = new HashMap<>();
        int n = s.length(), nxt = 0;
        int[] pat = new int[n];
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (!mp.containsKey(c)) mp.put(c, nxt++);
            pat[i] = mp.get(c);
        }
        return pat;
    }

    // 比较两个整型模式是否相同
    static boolean equalPattern(int[] a, int[] b) {
        if (a.length != b.length) return false;
        for (int i = 0; i < a.length; i++) if (a[i] != b[i]) return false;
        return true;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int t = Integer.parseInt(br.readLine().trim());
        StringBuilder ans = new StringBuilder();

        for (int cas = 0; cas < t; cas++) {
            int n = Integer.parseInt(br.readLine().trim());
            st = new StringTokenizer(br.readLine());
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) arr[i] = Integer.parseInt(st.nextToken());
            int[] base = patternFromArray(arr);

            int m = Integer.parseInt(br.readLine().trim());
            for (int i = 0; i < m; i++) {
                String s = br.readLine().trim();
                if (s.length() != n) {
                    ans.append("NO\n");
                } else {
                    int[] pat = patternFromString(s);
                    ans.append(equalPattern(base, pat) ? "YES\n" : "NO\n");
                }
            }
        }
        System.out.print(ans.toString());
    }
}

C++

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

// 将整型数组按首次出现顺序压缩为模式
vector<int> patternFromArray(const vector<long long>& a) {
    unordered_map<long long,int> mp; // 值 -> 首次编号
    vector<int> pat; pat.reserve(a.size());
    int nxt = 0;
    for (auto v : a) {
        if (!mp.count(v)) mp[v] = nxt++;
        pat.push_back(mp[v]);
    }
    return pat;
}

// 将字符串按首次出现顺序压缩为模式
vector<int> patternFromString(const string& s) {
    // 由于题中是小写字母，也可用数组；这里用 map 写法统一
    int n = (int)s.size();
    vector<int> pat; pat.reserve(n);
    vector<int> pos(256, -1);  // 字符 -> 首次编号，-1 表示未出现
    int nxt = 0;
    for (char c : s) {
        unsigned char uc = (unsigned char)c;
        if (pos[uc] == -1) pos[uc] = nxt++;
        pat.push_back(pos[uc]);
    }
    return pat;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; 
    if (!(cin >> t)) return 0;
    while (t--) {
        int n; cin >> n;
        vector<long long> a(n);
        for (int i = 0; i < n; ++i) cin >> a[i];
        vector<int> base = patternFromArray(a);

        int m; cin >> m;
        for (int i = 0; i < m; ++i) {
            string s; cin >> s;
            if ((int)s.size() != n) {
                cout << "NO\n";
                continue;
            }
            vector<int> pat = patternFromString(s);
            cout << (pat == base ? "YES\n" : "NO\n");
        }
    }
    return 0;
}

题目内容

小Q在路上捡到了一张字条，上面写了一个数组 $a$ 。小Q猜测这些数字可能是某种凯撒密码，于是他找来了一堆字符串，请你判断他找来的字符串能否匹配字条上的数字模板?

当字符串 $s$ 同时满足以下所有条件时，视为匹配模板:

• 字符串 $s$ 的长度等于数组 $a$ 的元素数量。

• 数组 $a$ 中相同的数字对应字符串 $s$ 中相同的字符。即，若 $a_i=a_j$ ,则 $s_i=s_j(1<=i,j<=n)$

• 字符串 $s$ 中相同的字符对应数组 $a$ 中相同的数字。即,若 $s_i=s_j$,则 $a_i=a_j(1≤i,j≤n)$.

换句话说，字符串的字符与数组元素之间必须存在对应关系。

例如,若 $a=[3,5,2,1,3]$，则字符串“$abfda$”匹配模板，而“$afbfa$”不匹配,因为字符“$f$” 对应数字 $1$ 和 $5$ .

输入描述

单个测试用例包含多组数据，第一行输入一个整数 $t(1<=t<=10^5)$ ，表示数据的数量.对于每组数据:

第一行包含一个整数 $n(1<=n<=2•10^5)$，表示数组 $a$ 的元素数量.

第二行包含恰好 $n$ 个整数$a_i(-10^9≤a_i≤10^9)$ 表示数组 $a$ 的元素。

第三行包含一个整数 $m(1≤m≤2•10^5)$，表示需要检查的字符串数量。

接下来 $m$ 行，每行包含一个非空字符串 $s_j(1≤|s_j|≤2•10^5)$ ，由小写字母组成。

保证所有测试用例的 $n$ 之和不超过 $2•10^5$，所有字符串长度之和不超过 $2•10^5$ .

输出描述

每个测试用例输出 $m$ 行。如果第 $1$ 个字符串匹配模板，第 $i$ 行输出 $YES$ ，否则输出 $NO$ (注意输出为大写)。

样例1

**输入

3
5
3 5 2 1 3
2
abfda
afbfa
2
1 2
3
ab
abc
aa
4
5 -3 5 -3
4
aaaa
bcbc
aba
cbcb

输出

YES
NO
YES
NO
NO
NO
YES
NO
YES