codeforces 1187 B

题意

有一个长度为n(0 < n <= \(2 * 10^5\))的字符串,有m(0 < m <= \(5 * 10^4\))次询问，每次询问输入一个字符串t(0 < |t| <= \(2 * 10^5\)),从n串里面取出所有a串的元素，需要取到第几个元素？(\(\quad\sum_{i=1}^{m}|t_i|≤2⋅10^5\))

题解

直接暴力是会超时的，用一个二维数组来记录每一个字符出现的位置，然后每次询问就可以直接输出最靠后的那个位置就可以了（代码更好懂

#include 
    
     #include 
     
      int cnt[300], cntt[300];//记录字符出现的次数int l[30][200010];//记录位置int main() {    int n, t, ans;    char s[200010], a[200010];    scanf("%d %s %d", &n, s, &t);    for(int i = 0; i < n; i++) {        l[s[i] - 'a'][cnt[s[i]]++] = i;    }    while(t--) {        scanf("%s", a);        int m = strlen(a), ans = 0;        memset(cntt, 0, sizeof(cntt));        for(int i = 0; i < m; i++) {            if(l[a[i] - 'a'][cntt[a[i]]] > ans) ans = l[a[i] - 'a'][cntt[a[i]]];            cntt[a[i]]++;        }        printf("%d\n", ans + 1);    }    return 0;}