POJ--1056 IMMEDIATE DECODABILITY && POJ--3630 Phone List（字典树）

题目大意看输入的每个字符串中是否有一个字符串是另一个字符串的前缀

#include<iostream>
#include<cstring>
#include<algorithm>
#include<string.h>
#include<stdio.h>
using namespace std;
#define maxn 10001
string b[maxn];
int tot=0;
struct ac{
   int sum,fa,nex[30];
   void init(){
     sum=0;fa=0;
     memset(nex,0,sizeof(nex));
   }
}tre[maxn*4];
void add(char a[],bool &f){
   int i=0,j=0,k=0;
   while(a[i]){
       int z=a[i]-'0';
       if(tre[k].nex[z]){
          j=tre[k].nex[z];
          tre[j].sum++;
          if(tre[j].fa) f=1;
       }else{
          tre[k].nex[z]=++tot;
          j=tot;
          tre[j].init();
          tre[j].sum++;
       }
       k=j;
       i++;
   }
   tre[k].fa++;
}
/*bool query(string a){
   int i=0,j=0,k=0;
   while(i<a.size()-1){
      int z=a[i]-'0';
      if(tre[k].nex[z]){
         j=tre[k].nex[z];
         if(tre[j].fa) return 1;
      }else return 0;
      k=j;
      i++;
   }
}*/
int main(){
   char a[1001];
   int len=0,tt=1;
   bool fa=0;
   while(scanf("%s",a)!=EOF){
      if(a[0]!='9'){
         add(a,fa);
      }else{
         if(fa)
            printf("Set %d is not immediately decodable
",tt++);
         if(!fa){
             printf("Set %d is immediately decodable
",tt++);
         }
         len=0;tot=0,fa=0;
         memset(tre,0,sizeof(tre));
      }
   }
}

题目链接： POJ--3630 Phone List

题意和上一个题差不多都是找里面是否含有前缀和相同的

#include<iostream>
#include<cstring>
#include<algorithm>
#include<string.h>
#include<stdio.h>
using namespace std;
#define maxn 100010
int tot=0;
struct ac{
   int sum,fa,nex[11];
   void init(){
     sum=0;fa=0;
     memset(nex,0,sizeof(nex));
   }
}tre[maxn];
void add(char a[],bool &f){
   int i=0,j=0,k=0;
   while(a[i]){
       int z=a[i]-'0';
       if(tre[k].nex[z]){
          j=tre[k].nex[z];
          tre[j].sum++;
          if(i==strlen(a)-1) f=1;
          if(tre[j].fa) f=1;
       }else{
          tre[k].nex[z]=++tot;
          j=tot;
          tre[j].init();
          tre[j].sum++;
       }
       k=j;
       i++;
   }
   tre[k].fa++;
}
/*bool query(string a){
   int i=0,j=0,k=0;
   while(i<a.size()-1){
      int z=a[i]-'0';
      if(tre[k].nex[z]){
         j=tre[k].nex[z];
         if(tre[j].fa) return 1;
      }else return 0;
      k=j;
      i++;
   }
}*/
char a[1001];
int main(){
   int t;
   cin>>t;
   while(t--){
      int n;
      scanf("%d",&n);
      memset(tre,0,sizeof(tre));
      tot=0;
      bool fa=0;
      for(int j=0;j<n;j++){
          scanf("%s",a);
          if(!fa)
          add(a,fa);
      }
      if(fa){
         printf("NO
");
      }else{
         printf("YES
");
      }
   }
}

POJ--1056 IMMEDIATE DECODABILITY && POJ--3630 Phone List（字典树）

相关推荐