Skip to content

14122: 【原4122】单词背诵

题目

题目描述

author: Ca. 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4122

Description

小X有n个单词想要背,但他想通过一篇文章中的一段来记住这些单词。文章由m个单词构成,他想在文章中找出连续的一段,其中包含最多的他想要背的单词(重复的只算一个)。并且在背诵的单词量尽量多的情况下,还要使选出的文章段落尽量短,这样他就可以用尽量短的时间学习尽可能多的单词了。

Input Format

第一行包含一个整数n。 接下来n行,每行包含一个长度不超过10的字符串,表示一个要背的单词。 接下来一行包含一个整数m。 接下来m行,每行包含一个长度不超过10的字符串,表示文章中的一个单词。

Output Format

第一行包含一个整数,表示文章中最多包含的要背的单词数。 第二行包含一个整数,表示在文章中包含最多要背单词的最短的连续段的长度。

Sample Input

3
hot
dog
milk
5
hot
dog
dog
milk
hot

Sample Output

3
3

Data Range

30%的数据,1≤n≤50,1≤m≤500。 60%的数据,1≤n≤300,1≤m≤5000。 100%的数据,1≤n≤1000,1≤m≤10^5。

q4x3's solution

/**
 * 字符串hash + 尺取法
 **/
#include <iostream>
#include <cstring>
#define ull unsigned long long

using namespace std;

int n, m, ans1, ans2, cur[100233];
char wor[1233][15], txt[100233][15];
bool wor_bool[100233];
ull wor_hash[100233], txt_hash[100233];
const ull base = 131;

template <typename T>
void merge(int lo, int mi, int hi, T* a)
{
    T* A = a + lo;
    int lb = mi - lo;
    T* B = new T[lb];
    T* BB = B;
    for(int i = 0;i < lb;++ i)
        B[i] = A[i];
    int lc = hi - mi;
    T* C = a + mi;
    int cnt = 0;
    while(1) {
        if ((lb == 0) && (lc == 0)) break;
        if (lb == 0) {
            A[cnt] = C[0];
            ++ cnt; ++ C; -- lc;
        }
        else if (lc == 0) {
            A[cnt] = B[0];
            ++ cnt; ++ B; --lb;
        }
        else {
            if(B[0] < C[0]) {
                A[cnt] = B[0];
                ++ cnt; ++ B; -- lb;
            }
            else {
                A[cnt] = C[0];
                ++ cnt; ++ C; -- lc;
            }
        }
    }
    delete []BB;
}

template <typename T>
void mergeSort(int lo, int hi, T* A)
{
    if(hi - lo < 2) return;
    int mi = (lo + hi) / 2;
    mergeSort(lo, mi, A); mergeSort(mi, hi, A);
    merge(lo, mi, hi, A);
}

ull myhash(char *s) {
    int len = strlen(s);
    ull tmp = 0;
    for(int i = 0;i < len;++ i) {
        tmp = tmp * base + (ull)s[i];
    }
    return tmp;
}

int binary_search(ull a) {
    int l = 1, r = n + 1;
    while(l < r) {
        int mid = (l + r) >> 1;
        if(wor_hash[mid] >= a) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    if(wor_hash[l] == a) return l;
    else if(wor_hash[r] == a) return r;
    else return 0;
}

bool check() {
    for(int i = 1;i <= n;++ i) {
        if(wor_bool[i]) {
            if(cur[i] == 0) return 0;
        }
    }
    return 1;
}

int main() {
    scanf("%d", &n);
    for(int i = 1;i <= n;++ i) 
        scanf("%s", wor[i]);
    scanf("%d", &m);
    for(int i = 1;i <= m;++ i) 
        scanf("%s", txt[i]);
    for(int i = 1;i <= n;++ i)
        wor_hash[i] = myhash(wor[i]);
    for(int i = 1;i <= m;++ i)
        txt_hash[i] = myhash(txt[i]);
    mergeSort(1, n + 1, wor_hash);
    for(int i = 1;i <= m;++ i) {
        int tmp = binary_search(txt_hash[i]);
        if(tmp && (! wor_bool[tmp])) {
            wor_bool[tmp] = 1;
            ++ ans1;
        }
    }
    int p = 1, q = ans1;
    ans2 = m;
    for(int i = p;i <= q;++ i) {
        int tmp = binary_search(txt_hash[i]);
        if(tmp) ++ cur[tmp];
    }
    if(ans1 == 0) ans2 = 0;
    else {
        while(q <= m) {
            if(check()) {
                ans2 = (q - p + 1 < ans2) ? q - p + 1 : ans2;
                int tmp = binary_search(txt_hash[p]);
                if(tmp) -- cur[tmp];
                ++ p;
            }
            else {
                ++ q;
                int tmp = binary_search(txt_hash[q]);
                if(tmp) ++ cur[tmp];
            }
        }
    }
    cout << ans1 << endl << ans2 << endl;
}

victrid's solution

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
//???Why?
unsigned long long bhash(char* c) {
    unsigned long long pc = 0;
    while (*c != '\0') {
        pc *= 131;
        pc += *c;
        c++;
    }
    return pc;
}
template <typename T1, typename T2>
struct paar {
    T1 __hash;
    T2 index;
    bool operator>(paar<T1, T2>& p) {
        return __hash > p.__hash;
    }
    bool operator<(paar<T1, T2>& p) {
        return __hash < p.__hash;
    }
    bool operator==(paar<T1, T2>& p) {
        return __hash == p.__hash;
    }
};

template <typename T>
class AVL {
protected:
    struct node {
        node* left;
        node* right;
        int height;
        T value;
    };
    node* data;
    int __size;
    node* i_query(node* root, T& to_query) {
        if (root == nullptr)
            return nullptr;
        if (root->value == to_query)
            return root;
        if (root->value > to_query) {
            return i_query(root->left, to_query);
        }
        if (root->value < to_query) {
            return i_query(root->right, to_query);
        }
    }
    void setrootheight(node* root) {
        if (root == nullptr)
            return;
        root->height = max((root->left == nullptr ? 0 : root->left->height), (root->right == nullptr ? 0 : root->right->height)) + 1;
    }

    node* right_rotate(node*& root) {
        node* nl   = root->left;
        root->left = nl->right;
        nl->right  = root;
        root       = nl;
        setrootheight(root->left);
        setrootheight(root->right);
        setrootheight(root);
        return root;
    }

    node* left_rotate(node*& root) {
        node* nr    = root->right;
        root->right = nr->left;
        nr->left    = root;
        root        = nr;
        setrootheight(root->left);
        setrootheight(root->right);
        setrootheight(root);
        return root;
    }

    inline int getfactor(node*& root) {
        if (root == nullptr)
            return 0;
        return (root->left == nullptr ? 0 : root->left->height) - (root->right == nullptr ? 0 : root->right->height);
    }

    int balance(node*& root) {
        if (root == nullptr)
            return 0;
        setrootheight(root->left);
        setrootheight(root->right);
        setrootheight(root);
        while (abs(getfactor(root->left)) > 1) {
            balance(root->left);
            setrootheight(root->left);
            setrootheight(root);
        }
        while (abs(getfactor(root->right)) > 1) {
            balance(root->right);
            setrootheight(root->right);
            setrootheight(root);
        }
        int p = getfactor(root);
        if (abs(p) <= 1)
            return 0;
        if (p > 0) {
            if (getfactor(root->left) == 1) {
                right_rotate(root);
                return 0;
            } else {
                left_rotate(root->left);
                right_rotate(root);
                return 0;
            }
        } else {
            if (getfactor(root->right) == -1) {
                left_rotate(root);
                return 0;
            } else {
                right_rotate(root->right);
                left_rotate(root);
                return 0;
            }
        }
    }

    int insert(node*& root, T& to_insert) {
        if (root == nullptr) {
            root = new node{nullptr, nullptr, 1, to_insert};
            __size++;
            return 0;
        }
        if (root->value < to_insert)
            insert(root->right, to_insert);
        else
            insert(root->left, to_insert);
        balance(root);
        return 0;
    }

    node* erasemin(node*& root) {
        if (root == nullptr)
            return nullptr;
        node* to_erase;
        if (root->left == nullptr) {
            to_erase = root;
            root     = root->right;
        } else {
            return erasemin(root->left);
        }
        balance(root);
        return to_erase;
    }

    int erase(node*& root, T& to_delete) {
        if (root == nullptr)
            return -1;
        if (root->value < to_delete)
            erase(root->right, to_delete);
        else if (root->value > to_delete)
            erase(root->left, to_delete);
        else if (root->value == to_delete) {
            __size--;
            node* rr = root;
            if (root->right == nullptr && root->left == nullptr) {
                root = nullptr;
            } else if (root->right == nullptr) {
                root = root->left;
            } else if (root->left == nullptr) {
                root = root->right;
            } else {
                node*& pp   = root->right;
                node* bl    = root->left;
                root        = erasemin(root->right);
                root->right = pp;
                root->left  = bl;
            }
            delete rr;
        }
        balance(root);
        return 0;
    }

public:
    AVL() : data(nullptr), __size(0){};
    int insert(T dat) {
        if (i_query(data, dat) != nullptr)
            return -1;
        else {
            insert(data, dat);
            return 0;
        }
    }
    int find(T dat) {
        return (i_query(data, dat) != nullptr);
    }
    int erase(T dat) {
        if (i_query(data, dat) == nullptr)
            return -1;
        else {
            erase(data, dat);
            return 0;
        }
    }
    int size() {
        return __size;
    }
};
class AVLtr : public AVL<paar<unsigned long long, int>> {
public:
    int test(unsigned long long t) {
        paar<unsigned long long, int> fp{t, __size + 1};
        node* f = i_query(data, fp);
        if (f == nullptr) {
            return -1;
        } else {
            return f->value.index;
        }
    }
};
int book[100005]   = {0};
int toremem[1005]  = {0};
int book_rem[1005] = {0};
inline bool checkrem(int n) {
    for (int i = 0; i < n; i++) {
        if (!toremem[i])
            continue;
        if (!book_rem[i])
            return false;
    }
    return true;
}
int main() {
    int n, m;
    scanf("%d", &n);
    char ch[100];
    AVLtr torem;
    for (int i = 0; i < n; i++) {
        scanf("%s", ch);
        torem.insert(paar<unsigned long long, int>{bhash(ch), i});
    }
    scanf("%d", &m);
    int exist_torem = 0;
    for (int i = 0; i < m; i++) {
        scanf("%s", ch);
        book[i] = torem.test(bhash(ch));
        if (book[i] != -1 && !toremem[book[i]]) {
            toremem[book[i]] = 1;
            exist_torem++;
        }
    }
    if (!exist_torem) {
        printf("0\n0");
        return 0;
    }
    // I was wrong.
    // two pointer method.
    // missing unchecked
    int *ptrl = book, *ptrr = book;
    book_rem[*ptrr]++;
    int flag = 0;
    int maxl = m;
    while (ptrr < book + m) {
        if (!checkrem(n)) {
            if (flag != 0) {
                maxl = min(maxl, flag);
            }
            ptrr++;
            if (*ptrr != -1) {
                book_rem[*ptrr]++;
            }
            flag = 0;
        } else {
            flag = ptrr - ptrl + 1;
            book_rem[*ptrl]--;
            ptrl++;
        }
    }
    printf("%d\n%d", exist_torem, maxl);
    return 0;
}