ACdream 1121 喵喵的IDE （Trie）

港控/mmm° 2022-06-09 07:12 141阅读 0赞

题目链接：  
[ACdream 1121][]

题意：  
中文题意。。。

题解：  
可以从缓存中进行三个操作，1.拿出字符串进行操作。2.删除末尾字符。3. 在末尾加入任意字符。  
让你求使得最小步数获得新的字符串并加入缓存中。  
可以用字典树(Trie)来存储字符串并进行查找。

AC代码：

#include <bits/stdc++.h>
    using namespace std;
    int ch[1000005][27],val[1000005];
    char s[1005];
    int sz = 1;
    int insert(char *s)
    {
        int u = 0;
        int c = 0;
        int len = 0, ans = 0 ;
        len = strlen(s);
        //最小初始化为自己长度
        ans = len;
        for(int i=0;i<len;i++) 
        {
            c = s[i] - 'a';
            if(!ch[u][c])
            {
                memset(ch[sz],0,sizeof(ch[sz]));
                val[sz] = 0x3f3f3f3f;
                ch[u][c] = sz++;
             }
             u = ch[u][c];
             //字符串长度 - 所走过的路 + 节点到叶子的长度
             ans = min(ans,len - i - 1 + val[u] + 1);
             //节点到叶子节点的最小值
             val[u] = min(val[u],len - i -1);
        }
        return ans;
    }
    int main()
    {
        int n,m;
        int t;
        scanf("%d",&t);
        while(t--)
        {
            memset(ch[0],0,sizeof(ch[0]));
            sz = 1;
            scanf("%d %s",&n,s);
            insert(s);
            while(n--)
            {
                scanf("%s",s);
                int ans = 0 ;
                ans = insert(s);
                printf("%d\n",ans);
             } 
        }
        return 0;
    }

[ACdream 1121]: http://acdream.info/problem?pid=1121

发表评论取消回复

表情：

评论列表（有 0 条评论，141人围观）

还没有评论，来说两句吧...

相关阅读

相关好奇喵 | Rust编程语言的简单了解~

![在这里插入图片描述][6ccc6ffecd934bedabb2096b1721b2c3.png] 前言有时候会听到别人谈论小众的语言，最近经常听到rust语言，感

我不是女神ヾ/ 2024年02月21日 09:14/ 0 赞/ 46 阅读

相关 2020.06.27 肉包去了喵星球

2020.06.27 17：34分肉包永远的离开了我们去了喵星球他肯定回去当他的小王子去了那么高冷帅气；本来打算让肉包再陪伴一周下去的时候鼻子出现了黄色

迷南。/ 2023年02月21日 01:56/ 0 赞/ 7 阅读

相关 ES隔断时间会莫名其妙删除索引…………我头上一堆小朋友**喵喵机器人？？还是病毒？？

现象：隔一两周，服务就嗝屁了，看日志大体造型就是有个【MetaDataDeleteIndexService】去删了索引……what a fck\\关键是你完全摸不着头脑……

悠悠/ 2022年12月09日 01:56/ 0 赞/ 179 阅读

相关爬取 20W 猫猫数据，来了解一下喵喵~

![format_png][] 点击上方“Python爬虫与数据挖掘”，进行关注回复“书籍”即可获赠Python从入门到进阶共10本电子书今日鸡汤来日

系统管理员/ 2022年10月29日 15:23/ 0 赞/ 199 阅读

相关洛谷P2336 喵星球上的点名

![1332167-20190308170133072-1732315604.png][] ![1332167-20190308170146031-1524629670.pn

淡淡的烟草味﹌/ 2022年10月02日 15:58/ 0 赞/ 136 阅读

相关爬虫-漫画喵的100行逆袭

小喵的唠叨话：这次的博客，讲的是使用python编写一个爬虫工具。为什么要写这个爬虫呢？原因是小喵在看完《极黑的布伦希尔特》这个动画之后，又想看看漫画，结果发现各大APP都没有

叁歲伎倆/ 2022年07月12日 11:43/ 0 赞/ 176 阅读

相关 ACdream 1063 平衡树（Trie树）

题目链接： [ACdream 1063][] 题意：让你设计一种数据结构，可以支持插入一个数，可以在这个数据结构里查询其中哪个数和给定的数的异或值最大或最小。题

淡淡的烟草味﹌/ 2022年06月12日 04:50/ 0 赞/ 117 阅读

相关 ACdream 1121 喵喵的IDE （Trie）

题目链接： [ACdream 1121][] 题意：中文题意。。。题解：可以从缓存中进行三个操作，1.拿出字符串进行操作。2.删除末尾字符。3. 在末尾加

港控/mmm°/ 2022年06月09日 07:12/ 0 赞/ 142 阅读

相关 Python学习笔记--画个可爱的叮当喵

参考大神的链接：你看过／写过哪些有意思的代码？ - 暴走的bug的回答 - 知乎 [https://www.zhihu.com/question/275611095/ans

你的名字/ 2022年05月22日 11:07/ 0 赞/ 115 阅读

相关小奶狗给小喵咪上CSS课程

![小奶狗给小喵咪上CSS课程][CSS] > 小奶狗给小喵咪上CSS课程小奶狗，你好啊？小喵咪你好~ 听说学习HTML，要学习CSS是吗？是

阳光穿透心脏的1/2处/ 2021年09月18日 09:48/ 0 赞/ 190 阅读