09月18日, 2016 3,093 views次
Link
http://acm.hdu.edu.cn/showproblem.php?pid=5880
Problem
Steam is a digital distribution platform developed by Valve Corporation offering digital rights management (DRM), multiplayer gaming and social networking services. A family view can help you to prevent your children access to some content which are not suitable for them.
Take an MMORPG game as an example, given a sentence T, and a list of forbidden words {P}, your job is to use ‘*’ to subsititute all the characters, which is a part of the substring matched with at least one forbidden word in the list (case-insensitive).
For example, T is: “I love Beijing’s Tiananmen, the sun rises over Tiananmen. Our great leader Chairman Mao, he leades us marching on.”
And {P} is: {“tiananmen”, “eat”}
The result should be: “I love Beijing’s *********, the sun rises over *********. Our gr*** leader Chairman Mao, he leades us marching on.”
Mean
给N个小写字母构成的单词,和一个文本串。要求把文本串中出现的所有单词置为星号并输出。串最长为1000000.
Analysis
这题是2016青岛区域赛网络赛的题目,最后一小时才看这道题,已经没有时间了,其实就是AC自动机水题,今天套个模板就1A了…好可惜….
首先将模板串加入到AC自动机,并且build一下。因为文本串中含有各种字符,我们可以将字母变为小写,其他字符变为‘z’+1。这样就能在自动机里统一处理,sigma_size = 27即可。
最后记录一下以每个字母为起点到右边最长禁止长度,最后输出一下就好了。
Code
#include <bits/stdc++.h> using namespace std; const int maxn = 1000100; char s[maxn], t[maxn]; int N, len[maxn], Len; int ban[maxn]; struct ACAutomate { static const int maxnode = maxn, sigma_size = 27; int ch[maxnode][sigma_size], val[maxnode], sz; int f[maxnode], last[maxnode]; void clear() { sz = 1; memset(ch[0], 0, sizeof(ch[0])); val[0] = 0; } int idx(char x) { return x - 'a'; } void insert(const char *s, int v) { int u = 0; for(int i = 0; s[i]; ++i) { int id = idx(s[i]); if(!ch[u][id]) { memset(ch[sz], 0, sizeof(ch[sz])); val[sz] = 0; ch[u][id] = sz++; } u = ch[u][id]; } val[u] = v; } void print(int j, int pos) { while(j) { if(val[j]) { int st = pos - len[val[j]] + 1; ban[st] = max(ban[st], len[val[j]]); } j = last[j]; } } void find(const char *T) { int j = 0, res = 0; for(int i = 0; T[i]; ++i) { int c = idx(T[i]); j = ch[j]; print(j, i); } } void getFail() { queue<int> qu; f[0] = 0; for(int c = 0; c < sigma_size; ++c) { int u = ch[0]; if(u) { f[u] = 0; qu.push(u); last[u] = 0; } } while(!qu.empty()) { int r = qu.front(); qu.pop(); for(int c = 0; c < sigma_size; ++c) { int u = ch[r]; if(!u) { ch[r] = ch[f[r]]; continue; } qu.push(u); int v = f[r]; while(v && !ch[v]) v = f[v]; f[u] = ch[v]; last[u] = val[f[u]] ? f[u] : last[f[u]]; } } } }ac; int main() { int T; scanf("%d", &T); while(T--) { scanf("%d", &N); ac.clear(); for(int i = 1; i <= N; ++i) { scanf("%s", s); len[i] = strlen(s); for(int j = 0; j < len[i]; ++j) s[i] = tolower(s[i]); ac.insert(s, i); } ac.getFail(); gets(s); gets(s); Len = strlen(s); for(int i = 0; i < Len; ++i) { if(isalpha(s[i])) t[i] = tolower(s[i]); else t[i] = 'a' + 26; } t[Len] = 0; memset(ban, 0, sizeof(ban)); ac.find(t); int R = -1; for(int i = 0; i < Len; ++i) { R = max(R, i + ban[i] - 1); if(i <= R) putchar('*'); else putchar(s[i]); } puts(""); } return 0; }