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(); } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |