记录编号	474939	评测结果	AAAAAAAAAAA
题目名称	文章过滤器	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.125 s
提交时间	2017-11-13 15:50:26	内存使用	0.56 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;

inline char getc(void) { 
    static char buf[1 << 18], *fs, *ft;
    return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
}

inline int read(void) { 
    char tmp = getc();
    int res = 0;
    while(!isdigit(tmp)) tmp = getc();
    while(isdigit(tmp)) 
        res = ((res + (res << 2)) << 1) + (tmp ^ 0x30),
        tmp = getc();
    return res;
}

inline int read(char *s) { 
    char *p = s;
    while(!isprint(*p = getc()));
    while(isprint(*(++p) = getc()));
    *p = '\0';
    return p - s;
}

#define seed (233)
#ifndef LOCAL
#   define MAXN (15010)
#else
#   define MAXN (100)
#endif
typedef unsigned long long ULL;

struct DATA{ ULL hash; int len;};

char str[MAXN], ans[MAXN];
vector<DATA> s;
int N, len;
ULL xp[MAXN], hs[MAXN], tmp;
int k[MAXN];

int main() { 
#ifndef LOCAL
    freopen("fliter.in", "r", stdin);
    freopen("fliter.out", "w", stdout);
#endif
    N = read();
    for(int i = 0; i < N; ++i) { 
        len = read(str);
        for(int i = 0; i < len; ++i)
            str[i] = tolower(str[i]);
        tmp = 0;
        for(int j = len - 1; ~j; --j)
            tmp = tmp * seed + str[j];
        s.push_back((DATA){tmp, len});
    }
    len = read(ans);
    for(int i = 0; i < len; ++i)
        str[i] = tolower(ans[i]);
    xp[0] = 1;
    for(int i = 1; i <= len; ++i)
        xp[i] = xp[i-1] * seed;
    for(int i = len - 1; ~i; --i)
        hs[i] = hs[i+1] * seed + str[i];
    for(int i = 0; i < N; ++i) { 
        for(int j = s[i].len; j <= len; ++j) { 
            if(s[i].hash == hs[j-s[i].len]-hs[j]*xp[s[i].len]) 
                k[j-s[i].len] = max(k[j-s[i].len], s[i].len);
        }
    }
    int i = 0;
    while(i < len) { 
        if(k[i]) for(int j = 0; j < k[i]; ++j)
            ans[i+j] = '*';
        ++i;
    }
    printf("%s\n", ans);
    return 0;
}