题目描述

难度分:$1300$

输入$n(1 \leq n \leq 2 \times 10^5)$和长为$n$的字符串$s$，只包含小写英文字母。

然后输入$m(1 \leq m \leq 5 \times 10^4)$和$m$个询问，每个询问输入一个长度$\leq 2 \times 10^5$字符串$t$，只包含小写英文字母。

保证所有$t$的长度之和$\leq 2 \times 10^5$。

对于每个询问，输出$s$的最短前缀长度，这个前缀包含一个子序列$p$，允许交换$p$中的字母，使得$p=t$。保证答案一定存在。

输入样例

9
arrayhead
5
arya
harry
ray
r
areahydra

输出样例

5
6
5
2
9

算法

统计

构建一个映射$mp$“字母$\rightarrow$该字母在$s$中出现的索引列表”，然后遍历每个名字$t_i$，统计其字母频数记录在$counter$中。遍历$26$个字母，只要$counter[c] \gt 0$，就维护$mp[c][counter[i]-1]$的最大值，即要凑满$counter[i]$个字母a$+i$要到达的最右索引，这个最大值就是答案。

复杂度分析

时间复杂度

遍历$s$串构建映射$mp$，时间复杂度为$O(n)$。之后遍历$t_i$，对每个名字，$O(m_i+\Sigma)$就能求得答案（其中$\Sigma=26$为字符集大小，$m_i$为$t_i$的长度）。

综上，算法整体的时间复杂度为$O(n+m+\Sigma_{i=1}^{m}|t_i|)$，$\Sigma_{i=1}^{m}|t_i|$是$O(n)$级别。

空间复杂度

$mp$映射存了$s$串$O(n)$级别个位置，之后遍历$t_i$，只需要开固定$O(\Sigma)$的空间统计每个$t_i$的字母频数就好。因此，整个算法的额外空间复杂度为$O(n+\Sigma)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    string s;
    cin >> n;
    cin >> s;
    unordered_map<char, vector<int>> mp;
    for(int i = 0; i < n; i++) {
        mp[s[i]].push_back(i);
    }
    int m;
    cin >> m;
    string t;
    vector<int> counter(26);
    while(m--) {
        cin >> t;
        for(int i = 0; i < 26; i++) counter[i] = 0;
        for(char c: t) counter[c - 'a']++;
        int ans = 0;
        for(int i = 0; i < 26; i++) {
            auto& pos = mp['a' + i];
            if(counter[i] > 0) {
                ans = max(ans, pos[counter[i] - 1]);
            }
        }
        cout << ans + 1 << '\n';
    }
    return 0;
}