hdu-2846 Repository-白红宇的个人博客

hdu-2846 Repository

发布日期：2021-09-06 22:32:36 浏览次数：4 分类：技术文章

本文共 1441 字，大约阅读时间需要 4 分钟。

思路：

好题，必须记一笔。

这题有两个之前没有接触过的字典树新变形。

第一个是insert的方式，不再只是单单的将一整个单词都插进去，而是从单词的第一个字母开始往后遍历，依次插入第i个字母到末尾的单词，这样做就可以满足题目中“substring”的要求，即将“substring”的问题转换为我们熟悉的字典树可以解决的“前缀”问题。

第二个是标记每个char* s所属的原始字符串，这种做法可以避免一个单词有相同部分的问题。

AC代码：

#include 
     
      #include 
      
       using namespace std;struct node{    int num;    int id;    struct node* next[26];    node()    {        num = 0;        id = -1;        for(int i = 0;i < 26;i++)            next[i] = NULL;    }};node* root;char str[10007][27];void Insert(char* s,int mark){    node* p = root;    for(;*s!='\0';s++)    {        int n = *s-'a';        if(p->next[n] == NULL) {            p->next[n] = new node();            p = p->next[n];            p->id = mark;            p->num = 1;        }        else {            p = p->next[n];            if(p->id != mark) {                p->id = mark;                p->num++;            }        }    }}int search(char* s){    node* p = root;    for(;*s!='\0';s++)    {        int n = *s-'a';        if(p->next[n] == NULL) return 0;        p = p->next[n];    }    return p->num;}int main(){    root = new node();    int P;    cin>>P;    for(int i = 0;i < P;i++)    {        cin>>str[i];        char* tmp = str[i];        for(;*tmp!='\0';tmp++)            Insert(tmp,i);    }    int tc;    cin>>tc;    char t[27];    while(tc--)    {        cin>>t;        cout<
       
        <

转载于:https://www.cnblogs.com/immortal-worm/p/5199943.html

转载地址：https://blog.csdn.net/weixin_34273481/article/details/93318523 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：[硬件]_ELVE_STLINK下载出现nternal command error问题

下一篇：HDU-1231,最大区间连续和总结-分治法-dp

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章