POJ 3630 && HDU 1671 Phone list（静态字典树）

HDU 1671

POJ 3630

静态字典树，动态会超时

方案一，结构体静态字典树，不排序，在插入时判断

#include <stdio.h>
#define  MAX    10 

typedef struct TrieNode
{
    int nEndFlag; //标记该字符是否是某一字符串的结尾
    struct TrieNode *next[MAX];
}TrieNode;

TrieNode Memory[1000000];
int allocp = 0 , nFlag = 0;

void InitTrieRoot(TrieNode **pRoot)
{
    *pRoot = NULL;
}

TrieNode *CreateTrieNode()
{
    int i;
    TrieNode *p;

    p = &Memory[allocp++];
    p->nEndFlag = 0;
    for(i = 0 ; i < MAX ; i++)
    {
        p->next[i] = NULL;
    }

    return p;
}

void InsertTrie(TrieNode **pRoot , char *s)
{
    int i , k;
    TrieNode *p;

    if(!(p = *pRoot))
    {
        p = *pRoot = CreateTrieNode();
    }
    i = 0;
    while(s[i])
    {
        k = s[i++] - '0'; 
        if(p->next[k])
        {
            if(p->next[k]->nEndFlag == 1 || s[i] == '') //先短后长 || 先长后短
            {
                nFlag = 1;
                return;
            }
        }
        else
        {
            p->next[k] = CreateTrieNode();
        }
        p = p->next[k];
    }
    p->nEndFlag = 1;  //标记结尾
}


int main(void)
{
    int  z , n , i;
    char s[11];    
    TrieNode *Root;  

    scanf("%d", &z);
    while(z-- > 0)  
    {       
        nFlag = allocp = 0;
        InitTrieRoot(&Root); 
        scanf("%d" , &n);    getchar();
        for(i = 0 ; i < n ; i++)
        {
            gets(s);
            if(!nFlag)    InsertTrie(&Root , s); 
        }
        nFlag ? printf("NO
") : printf("YES
");
    }    
  
    return    0;
}

方案二， 结构体静态字典树，先排序，后插入

#include <stdio.h>
#include <algorithm>
#include <iostream>
#include<cstring>
using namespace std;
#define  MAX    10
int flag = 0;
typedef struct TrieNode
{
	int nEndFlag; //标记该字符是否是某一字符串的结尾
	TrieNode * next[MAX];
} TrieNode;

TrieNode Memory[1000000];
int allocp = 0 , nFlag = 0;

void InitTrieRoot(TrieNode ** pRoot)
{
	*pRoot = NULL;
}

TrieNode * CreateTrieNode()
{
	int i;
	TrieNode * p;

	p = &Memory[allocp++];
	p->nEndFlag = 0;

	for (i = 0 ; i < MAX ; i++)
	{
		p->next[i] = NULL;
	}

	return p;
}

void InsertTrie(TrieNode ** pRoot , char * s)
{
	int i , k;
	TrieNode * p;

	if (!(p = *pRoot))
	{
		p = *pRoot = CreateTrieNode();
	}

	i = 0;

	while (s[i])
	{
		k = s[i++] - '0';
		if (!(p->next[k]))
		{
			p->next[k] = CreateTrieNode();
		}
		p = p->next[k];
		if(p->nEndFlag)
		{
			flag = 1;
			return;
		}
	}
	p->nEndFlag = 1;  //标记结尾
}
struct Code
{
	int len;
	char num[15];
}code[10005];

bool cmp(Code a, Code b)
{
	return a.len < b.len;
}
int main()
{
	//freopen("1.in","r",stdin);
	int  t, n;
	TrieNode  *root;
	cin >> t;

	while (t--)
	{
		nFlag = allocp = 0;
        InitTrieRoot(&root);
		int i = 0;
		cin >> n;
		getchar();

		while (n--)
		{
			gets(code[i].num);
			code[i].len = strlen(code[i].num);
			i++;
		}
		sort(code, code + i, cmp);
		for (int j = 0; j < i; j++)
		{
			InsertTrie(&root,code[j].num);
		}
		if (flag)
		{
			printf("NO
");
		}
		else
		{
			printf("YES
");
		}

		flag = 0;
	}
	return 0;
}

方案三 ， 二维数组的静态字典树，没有指针，一般不会非法内存访问之类的

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int ch[100005][10];
int val[100005];
int sz,flag;
int getid(char ch)
{
	return ch-'0';
}
void insert(char *s)
{
	int i,pre=0,now;
	for(i=0;s[i]!='';i++)
	{
		int id=getid(s[i]);
		now=ch[pre][id];
		if(!now)
		{
			memset(ch[sz],0,sizeof(ch[sz]));
			val[sz]=0;
			ch[pre][id]=sz;
			now=sz;
			sz++;
		}
		if(val[now]==1) //此字符串是前面某个字符串的前缀。
		{
			flag=1;
			return;
		}
		pre=now;
	}
	val[pre]=1;
	for(i=0;i<10;i++)   //前面某个字符串是此字符串的前缀。
		if(ch[pre][i])
		{
			flag=1;
			return;
		}
}
int main()
{
    int T,i,n;
	char str[11];
    scanf("%d",&T);
    while(T--)
    {
		flag=0;
        scanf("%d",&n);
		sz=1;
		memset(ch[0],0,sizeof(ch[0]));
        for(i=0;i<n;i++)
        {
            scanf("%s",str);
            if(!flag) insert(str);
        }
        if(flag) printf("NO
");
        else printf("YES
");
    }
    return 0;
}