Skip to content

14188: 【原4188】罪恶黑名单

题目

题目描述

author: DS TA 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4188

Description

联邦探员Elizabeth Keen得到了联邦探员Elizabeth Keen得到了 一份恐怖分子黑名单, 黑名单上有$N$个名字$S_i$, 每个名字$S_i$由连续的小写字母组成, 中间无空格或其它符号. 她对名字进行研究,试图找出 其中的联系.身为反恐团队中的计算机专家, 你需要回答她的三类问题: 类型1,问题为1 $x$,表示询问名字$S_x$是否在 $1\leqslant i < x$中的$S_i$出现. 若出现,请回答yes,否则请回答no. 类型2,问题为2 $x$ $y$,表示询问名字$S_x$, $S_y$的 最长公共前缀的长度. 类型3,问题为3 $x$ $y$,表示询问名字$S_x$, $S_y​$的 最长公共后缀的长度.

Input Format

第一行包含一个正整数$N$, 表示名字个数. 接下来$N$行,每行给出一个非空字符串, 表示名字$S_i$.保证字符串由连续的 小写字母组成,行前行末以及字符串中间没有空格. 接下来一行包含一个正整数$M$, 表示询问次数. 接下来$M$行,每行给出一个询问, 询问格式是上述三类问题的一种, 即1 $x$或2 $x$ $y$或3 $x$ $y$.

Output Format

输出$M$行,第$i$行输出第$i$个询问的答案.

Sample Input

2
goodluck
goodluck
1
1 1

Sample Output

no

Neight99's solution 

#include <iostream>
#include <string>

typedef unsigned long long ull;
typedef long long ll;

using namespace std;

const int maxN = 1e5 + 10;
string str[maxN];
int preHashpos[maxN] = {0}, sufHashpos[maxN] = {0};
ull strHash[maxN], preHash1[maxN] = {0}, sufHash1[maxN] = {0};

ull calHash(string str, int l, int r) {
    ull ans = 0;
    for (int i = l; i < r; i++) {
        ans = 131 * ans + (str[i] - 'a' + 1);
    }
    return ans;
}

void preHash(string str, ull *preHash) {
    preHash[0] = str[0] - 'a' + 1;
    for (int i = 1; i < str.length(); i++) {
        preHash[i] = 131 * preHash[i - 1] + (str[i] - 'a' + 1);
    }
}

void sufHash(string str, ull *preHash) {
    int len = str.length();
    preHash[0] = str[len - 1] - 'a' + 1;
    for (int i = 1; i < len; i++) {
        preHash[i] = 131 * preHash[i - 1] + (str[len - i - 1] - 'a' + 1);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N, M, order, x, y;

    cin >> N;
    str[0] = "";
    for (int i = 1; i <= N; i++) {
        cin >> str[i];
        strHash[i] = calHash(str[i], 0, str[i].length());
        preHashpos[i] = preHashpos[i - 1] + str[i - 1].length();
        sufHashpos[i] = sufHashpos[i - 1] + str[i - 1].length();
        preHash(str[i], &preHash1[preHashpos[i]]);
        sufHash(str[i], &sufHash1[sufHashpos[i]]);
    }

    cin >> M;
    for (int i = 0; i < M; i++) {
        cin >> order;
        switch (order) {
            case 1: {
                cin >> x;
                bool flag = 0;
                for (int i = 1; i < x; i++) {
                    if (strHash[i] == strHash[x]) {
                        flag = 1;
                        break;
                    }
                }
                if (flag) {
                    cout << "yes" << '\n';
                } else {
                    cout << "no" << '\n';
                }
                break;
            }
            case 2: {
                cin >> x >> y;
                int len1 = str[x].length(), len2 = str[y].length(),
                    len3 = len1 < len2 ? len1 : len2;
                int l = 0, r = len3 - 1, ans;
                ull *temp1 = &preHash1[preHashpos[x]],
                    *temp2 = &preHash1[preHashpos[y]];
                while (l <= r) {
                    int mid = (l + r) >> 1;
                    if (temp1[mid] == temp2[mid]) {
                        ans = mid + 1;
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
                cout << ans << '\n';
                break;
            }
            case 3: {
                cin >> x >> y;
                int len1 = str[x].length(), len2 = str[y].length(),
                    len3 = len1 < len2 ? len1 : len2;
                int l = 0, r = len3 - 1, ans;
                ull *temp1 = &sufHash1[sufHashpos[x]],
                    *temp2 = &sufHash1[sufHashpos[y]];
                while (l <= r) {
                    int mid = (l + r) >> 1;
                    if (temp1[mid] == temp2[mid]) {
                        ans = mid + 1;
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
                cout << ans << '\n';
                break;
            }
        }
    }
    return 0;
}

victrid's solution 

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int
    total;

unsigned long long
    len[1000005]   = {0},
    fhash[1000005] = {0},
    bhash[1000005] = {0},
    shash[1000005] = {0};

char
    buffer[1000005];

int main() {
    scanf("%d", &total);
    for (int i = 1; i <= total; i++) {
        scanf("%s", buffer);
        int s             = strlen(buffer);
        len[i]            = s + len[i - 1];
        fhash[len[i - 1]] = buffer[0];
        bhash[len[i] - 1] = buffer[s - 1];
        for (int j = 1; j < s; j++) {
            //...Hash number...
            fhash[len[i - 1] + j] = fhash[len[i - 1] + j - 1] * 1313 + buffer[j];
            bhash[len[i] - 1 - j] = bhash[len[i] - j] * 1313 + buffer[s - 1 - j];
        }
        shash[i] = fhash[len[i] - 1];
    }
    int times;
    scanf("%d", &times);
    for (int f = 0; f < times; f++) {
        int pg, pf, ps;
        scanf("%d", &ps);
        switch (ps) {
        case 1: {
            bool bf = false;
            scanf("%d", &pf);
            for (int i = 1; i < pf; i++) {
                if (shash[i] == shash[pf]) {
                    bf = true;
                    break;
                }
            }
            printf(bf ? "yes\n" : "no\n");
            break;
        }
        case 2: {
            scanf("%d %d", &pg, &pf);
            int szv = min(len[pg] - len[pg - 1], len[pf] - len[pf - 1]), i = 0;
            for (; i < szv; i++) {
                if (fhash[len[pg - 1] + i] != fhash[len[pf - 1] + i])
                    break;
            }
            printf("%d\n", i);
            break;
        }
        case 3: {
            scanf("%d %d", &pg, &pf);
            int szv = min(len[pg] - len[pg - 1], len[pf] - len[pf - 1]), i = 0;
            for (; i < szv; i++) {
                if (bhash[len[pg] - i - 1] != bhash[len[pf] - i - 1])
                    break;
            }
            printf("%d\n", i);
            break;
        }
        }
    }
    return 0;
}

zqy2018's solution 

/*
    Hint: use SAM and hash (or SA?)
*/
#include <bits/stdc++.h>
#define INF 2000000000
#define M 100007ull
using namespace std;
typedef unsigned long long ull;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
struct SAM{
    int len[300005], link[300005], to[300005][27];
    int last, D;
    int Sigma;
    SAM(int sigma){
        last = D = 0;
        Sigma = sigma;
        len[0] = 0, link[0] = -1;
        for (int i = 0; i < Sigma; ++i)
            to[0][i] = -1;
    }
    int create_node(){
        int res = ++D;
        link[res] = -1;
        for (int i = 0; i < Sigma; ++i)
            to[res][i] = -1;
        return res;
    }
    int copy_node(int src){
        int res = ++D;
        link[res] = link[src];
        for (int i = 0; i < Sigma; ++i)
            to[res][i] = to[src][i];
        return res;
    }
    inline int get_cid(char c){
        return (c == '#' ? 26: c - 'a');
    }
    void insert(char c){
        int cid = get_cid(c);
        int cur = create_node();
        len[cur] = len[last] + 1;
        int p = last;
        while (p != -1 && to[p][cid] == -1){
            to[p][cid] = cur;
            p = link[p];
        }
        if (p == -1){
            link[cur] = 0;
        }else {
            int q = to[p][cid];
            if (len[p] + 1 == len[q]){
                link[cur] = q;
            }else {
                int clone = copy_node(q);
                len[clone] = len[p] + 1;
                link[cur] = link[q] = clone;
                while (p != -1 && to[p][cid] == q){
                    to[p][cid] = clone;
                    p = link[p];
                }
            }
        }
        last = cur;
    }
    bool check(const string& s){
        int cur = 0, l = s.length();
        for (int i = 0; i < l; ++i){
            cur = to[cur][get_cid(s[i])];
            if (cur == -1) return false;
        }
        return true;
    }
    bool check(char* s, int l){
        int cur = 0;
        for (int i = 0; i < l; ++i){
            cur = to[cur][get_cid(s[i])];
            if (cur == -1) return false;
        }
        return true;
    }
};
SAM sam(27);
int n;
vector<vector<ull> > hsh_pre, hsh_suf;
bool ans[50005] = {0};
void init(){
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; ++i){
        string s;
        cin >> s;
        ans[i] = sam.check(s);
        for (char c: s)
            sam.insert(c);
        sam.insert('#');

        hsh_pre.push_back(vector<ull>());
        vector<ull>& v1 = hsh_pre.back();
        v1.push_back(0);
        ull lst = 0;
        for (char c: s)
            lst = lst * M + c - 'a', 
            v1.push_back(lst);

        hsh_suf.push_back(vector<ull>());
        vector<ull>& v2 = hsh_suf.back();
        v2.push_back(0);
        lst = 0;
        int l = s.length();
        for (int i = l - 1; i >= 0; --i)
            lst = lst * M + s[i] - 'a', 
            v2.push_back(lst);
    }
}
int lcp(vector<ull>& v1, vector<ull>& v2){
    int l = 0, r = max(v1.size(), v2.size());
    --r;
    while (r > l){
        int mid = (l + r + 1) >> 1;
        if (v1[mid] == v2[mid])
            l = mid;
        else r = mid - 1;
    }
    return l;
}
void solve(){
    int q;
    cin >> q;
    while (q--){
        int opr;
        cin >> opr;
        if (opr == 1){
            int t;
            cin >> t;
            printf("%s\n", (ans[t - 1] ? "yes": "no"));
        }
        if (opr == 2){
            int x, y;
            cin >> x >> y;
            printf("%d\n", lcp(hsh_pre[x - 1], hsh_pre[y - 1]));
        }
        if (opr == 3){
            int x, y;
            cin >> x >> y;
            printf("%d\n", lcp(hsh_suf[x - 1], hsh_suf[y - 1]));
        }
    }
}
int main(){
    init();
    solve();
    return 0;
}