题意:有两个字符串 a 和 b,问 b 中有多少个本质不同子串可以由 a 删除若干个字符得到。
|a|,|b|<=3000
题解:字典树(这个题做法很多,后补)。
把字符串 b 的每个子串打到字典树上。
然后因为 3000^2*26 这个东西比较大,所以不能用 nxt[id][26] 来存储,于是使用链式前向星存图,这样 trie 就建出来了。
接下来考虑如何统计答案。因为要做的是本质不同子串,所以考虑如果 a 是
a.....b.....b
那么我在 a 之后接上第一个 b 肯定比接上第二个 b 优。就是说如果我取 a 的子串是 ab.... 那么这个 b 一定取得是前面那个 b。
这个证明不难。
所以说我对于每个位置去转移,只会考虑这个位置之后的第一个 a/b/c/.../z。
那就好办了。我存储每个位置之后的第一个 a/b/c/../z,然后如果字典树上做到了这个节点,同时能够向下转移的话就直接转移。转移每一位都意味着答案加一。
代码直接放上来以防文字太抽象
struct edge {
int to, nxt, val;
} e[10000000];
int head[10000000], cnt, triecnt, n;
void add(int u, int v, int w) {
e[++cnt].to = v;
e[cnt].nxt = head[u];
e[cnt].val = w;
head[u] = cnt;
}
char a[4000], b[4000];
int ind[30], nxta[4000][30];
void insert(int x) {
int p = 0;
for(int i = x; i <= n; ++i) {
int flag = 0;
for(int j = head[p]; j; j = e[j].nxt) if(e[j].val == b[i] - 'a') {
flag = 1;
p = e[j].to;
break;
}
if(!flag) {
add(p, ++triecnt, b[i] - 'a');
p = triecnt;
}
}
}
int ans;
void find(int u, int a) {
for(int i = head[u]; i; i = e[i].nxt) if(nxta[a][e[i].val] != -1) {
++ans;
find(e[i].to, nxta[a][e[i].val]);
}
}
int main() {
ios::sync_with_stdio(0);
scanf("%d%s%s", &n, a+1, b+1);
memset(ind, -1, sizeof(ind));
for(int i = n; i >= 0; --i) {
for(int j = 0; j < 26; ++j) nxta[i][j] = ind[j];
if(i) ind[a[i] - 'a'] = i;
}
for(int i = 1; i <= n; ++i) insert(i);
find(0, 0);
cout << ans;
return 0;
}
标签:子串,cnt,P7469,洛谷,int,题解,26,ind
From: https://www.cnblogs.com/1358id/p/17373170.html