昵称检索
#贪心 #前缀和
给定一个字符串 $S$，请计算从中删去一部分字符后（可以什么都不删），可以得到多少个本质不同的’’昵称’’。
一个字符串被认为是’’昵称’’当且仅当它可以被划分成前后两个部分，第一个部分是给定的 n 个名字之一，第二个部分长度固定四位，表示生日。
例如第一个样例中，可以得到的’’昵称’’分别为：’’kevin0724’’、’’kevin0729’’、’’kevin0924’’、’’kevin0929’’。
Input
第一行包含一个正整数 $T$ (1≤T≤100)，表示测试数据的组数。
每组数据第一行包含两个正整数 n,m (1≤n≤1e5, 1≤m≤1e6)，分别表示名字的数量以及字符串 $S$ 的长度。
第二行包含一个长度为 m 的字符串 S，由数字和小写英文字母构成。
接下来 n 行，每行一个长度在[1,20] 之间的仅由小写英文字母构成的字符串 $name_i$，表示一个名字。输入数据保证名字两两不同。
输入数据保证 $∑$m≤7000000，且 $∑$|name|≤7000000
Output
对于每组数据输出一行一个整数，即能得到的本质不同的’’昵称’’数量。
题解
一个名字可能出现多次，贪心，显然只需要找到它第一次完整出现时最后一个字符的位置
关键在于构建loc数组
对于每个字符在字符串中的每一个位置，存储向左/向右离它最近的相同字符的位置
这样能用$O(n)$的时间复杂度得到第一次完整出现的位置
生日的组合有365种，（2月算29天）
遍历一年的每一天，从后往前跳转4次，在数组里存下该位置，说明只要在这个位置之前的名字，都能取这一天。
求后缀和，跳转到第一次完整出现的位置然后累加。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define IOS ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)
int day[13] = {
0,31,29,31,30,31,30,31,31,30,31,30,31
};
const int N = 1000001;
int loc1[26][N];
int loc2[10][N];
int suf[N];
string name[100001];
string s;
void solve() {
IOS;
int q, m,n,ans = 0;
cin >> q >> n >> s;
s = 'A' + s;
for (int i = 1; i <= q; i++) {
cin >> name[i];
}
for(int i = 0; i <= 25; i++) {
int latest = n+1;
for(int j = n; j >= 1; j--) {
if(s[j] - 'a' == i) {
latest = j;
}
loc1[i][j] = latest;
}
}
for(int i = 0; i <= 9; i++) {
int latest = 0;
for(int j = 1; j <= n; j++) {
if(s[j] - '0' == i) {
latest = j;
}
loc2[i][j] = latest;
}
}
for(int i = 1; i <= n; i++) suf[i] = 0;
for(int i = 1; i <= 12; i++) {
for(int j = 1; j <= day[i]; j++) {
int date[5];
date[1] = i/10;
date[2] = i%10;
date[3] = j/10;
date[4] = j%10;
int cur = n;
for(int k = 4; k >= 1; k--) {
assert(date[k] < 10);
cur = loc2[date[k]][cur];
if(cur == 0) break;
cur--;
}
if(cur != 0) suf[cur]++;
}
}
for(int i = n-1; i >= 1; i--) suf[i] += suf[i+1];
for(int i = 1; i <= q; i++) {
int cur = 1;
for(char& j : name[i]) {
assert(j-'a' < 26);
cur = loc1[j-'a'][cur];
if(cur == n+1) break;
cur++;
}
if(cur != n+1) ans += suf[cur];
}
cout<<ans<<endl;
}
int main() {
IOS;
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}