加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 (https://www.lidatong.com.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 大数据 > 正文

Pj Immediate Decodability

发布时间:2020-12-14 03:23:28 所属栏目:大数据 来源:网络整理
导读:判断一个串是否是其他的前缀 我们需要建立一颗tire树 在插入边的时候,如果遇到一个其他串的结尾,那么就说明至少有一个串,是插入串的前缀。如果在插入完后没有新增的节点,那么插入的串就是其他串的前缀 #includecstdio #includealgorithm #includeiostrea

判断一个串是否是其他的前缀

我们需要建立一颗tire树

在插入边的时候,如果遇到一个其他串的结尾,那么就说明至少有一个串,是插入串的前缀。如果在插入完后没有新增的节点,那么插入的串就是其他串的前缀

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int manx=1<<8;
char data[manx];
int t[manx][2],tail;
int end[manx<<8];
bool flag=false;
void ins()
{
    int last=tail,now=0;
    int len=strlen(data)-1;
    for(int i=0;i<=len;i++)
    {
        int nxt=data[i]-'0';
        if(!t[now][nxt])    t[now][nxt]=++tail;
        if(end[now])    flag=true;//经过一个串的结尾
        now=t[now][nxt];
    }
    end[now]+=1;
    if(last==tail)  flag=true;//是其他串的前缀
    return ;
}
int main()
{
    int tot=0;
    //freopen("a.in","r",stdin);
    while(scanf("%s",data)!=EOF)
    {
        if(data[0]=='9')
        {
            tot+=1;
            if(!flag)
                printf("Set %d is immediately decodablen",tot);
            else
            {
                printf("Set %d is not immediately decodablen",tot);
            }//每一组数据都要初始化
            flag=false;
            memset(t,0,sizeof(t));
            memset(end,sizeof(end));
            tail=0;
            continue;
        }
        if(!flag)   ins();
    }
}

(编辑:李大同)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    推荐文章
      热点阅读