ACdream 1121 喵喵的IDE （Trie）

港控/mmm° 2022-06-09 07:12 162阅读 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