指针 照着第一篇题解写的 10pts 求调
查看原帖
指针 照着第一篇题解写的 10pts 求调
204926
富乐人呃呃呃楼主2021/12/28 17:33
#include<set>
#include<ctime>
#include<queue>
#include<bitset>
#include<cstdio>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<ext/pb_ds/assoc_container.hpp>

typedef long long ll;

constexpr int maxn = 1e5 + 100;

struct Node;
struct Result;
typedef Node* lpNode;
typedef Result Res;

extern lpNode root;
extern const lpNode nil;

struct Node
{
    lpNode fail;
    lpNode vis[26];
    int end;
} pool[maxn];
Node null;
const lpNode nil = &null;
lpNode root = pool;

int cnt = 0;

struct Result
{
    int num;
    int pos;
    friend bool operator<(const Res &lhs, const Res &rhs)
    {
        if (lhs.num != rhs.num)
            return lhs.num > rhs.num;
        else
            return lhs.pos < rhs.pos;
    }
} Ans[maxn];

std::string s[maxn];

lpNode init()
{
    auto tmp = pool + (cnt++);
    for (auto &p : tmp->vis)
        p = nil;
    tmp->fail = root;
    tmp->end = 0;
    return tmp;
}

void insert(const std::string &s, int Num)
{
    int len = s.length();
    auto cur = root;
    for (int i = 0; i < len; ++i)
    {
        if (cur->vis[s[i] - 'a'] == nil)
            cur->vis[s[i] - 'a'] = init();
        cur = cur->vis[s[i] - 'a'];
    }
    cur->end = Num;
}

void getFail()
{
    std::queue<lpNode> Q;
    for (int i = 0; i < 26; ++i)
        if (root->vis[i] != nil)
        {
            root->vis[i]->fail = root;
            Q.push(root->vis[i]);
        }
    while (!Q.empty())
    {
        auto p = Q.front();
        Q.pop();
        for (int i = 0; i < 26; ++i)
            if (p->vis[i] != nil)
            {
                p->vis[i]->fail = p->fail->vis[i];
                Q.push(p->vis[i]);
            }
            else
                p->vis[i] = p->fail->vis[i];
    }
}

int Query(std::string s)
{
    int len = s.length();
    auto cur = root;
    // int ans = 0;
    for (int i = 0; i < len; ++i)
    {
        cur = cur->vis[s[i] - 'a'];
        for (auto t = cur; t != nil; t = t->fail)
            Ans[t->end].num++;
    }
    // return ans;
}

int canselSync =   (std::ios::sync_with_stdio(0),
                    std::cin.tie(0),
                    std::cout.tie(), 0);

signed main()
{
    int n;
    nil->fail = nil;
    for (auto &p : nil->vis)
        p = nil;
    while (1)
    {
        std::cin >> n;
        if (n == 0)
            break;
        cnt = 0;
        root = init();
        for (int i = 1; i <= n; ++i)
        {
            std::cin >> s[i];
            Ans[i].num = 0;
            Ans[i].pos = i;
            insert(s[i], i);
        }
        root->fail = nil;
        getFail();
        std::cin >> s[0];
        Query(s[0]);
        std::sort(Ans + 1, Ans + 1 + n);
        std::cout << Ans[1].num << "\n";
        std::cout << s[Ans[1].pos] << "\n";
        for (int i = 2; i <= n; ++i)
            if (Ans[i].num == Ans[i - 1].num)
                std::cout << s[Ans[i].pos] << '\n';
            else
                break;
    }
    return 0;
}

2021/12/28 17:33
加载中...