字符串前缀匹配 trie boj1212

Phone ListSubmit: 106   Accepted:44Time Limit: 1000MS  Memory Limit: 65536KDescription
Given a list of phone numbers, determine if it is consistent in the sense that no number is the prefix of another. Let’s say the phone catalogue listed these numbers:
Emergency 911
Alice 97 625 999
Bob 91 12 54 26
In this case, it’s not possible to call Bob, because the central would direct your call to the emergency line as soon as you had dialled the first three digits of Bob’s phone number. So this list would not be consistent.


Input
he first line of input gives a single integer, 1 <= t <= 40, the number of test cases. Each test case starts with n, the number of phone numbers, on a separate line, 1 <= n <= 10000. Then follows n lines with one unique phone number on each line. A phone number is a sequence of at most ten digits.


Output
For each test case, output “YES” if the list is consistent, or “NO” otherwise.


Sample Input

2
3
911
97625999
91125426
5
113
12340
123440
12345
98346


Sample Output

NO
YES


Source
NCPC 2007


题意：给定一组字符串，确定其中是否有某个字符串是其他字符串的前缀。
思路：第一想到的就是trie。这里需要主义的是trie的设计问题：
   1.达到字符串结尾时，设置一个终结符，MAX_INT，表示这是字符串最后一个字符
   2.当较短的字符A匹配上较长的字符B时，trie中的数据不会有任何改变
   3.当较长的字符A匹配上较短的字符B时，会遇到MAX_INT值。
   考虑到2和3这两个情况就行了。


#include 
#include 

#define MAX_INT 0x7fffffff

int trie[100000][10], length;
char string[15];

int check_prefix(char *string)
{
    int start = 0, next = 0, have_prefix;
    while ('\0' != *string)
    {
        have_prefix = 1;
        next = *string - '0';
        if (MAX_INT == trie[start][next])/*长字符串前缀匹配上短字符串*/
            return 1;
        if (trie[start][next] == 0)
        {
            have_prefix = 0;             /*trie中数值改变，说明没有存在这个字符串的前缀*/
            if (*(string+1) != '\0')
            {
                trie[start][next] = ++length;
            }
            else
            {
                trie[start][next] = MAX_INT;
                start = ++length;
                string++;
                continue;
            }
        }
        start = trie[start][next];
        string++;
    }
    return have_prefix;
}

int main(int argc, char *argv[])
{
    int t, i, j, n, check;
    scanf("%d", &t);
    for (i=0 ; i    {
        memset(trie, 0, sizeof(trie));
        length = 0;
        scanf("%d", &n);
        check = 0;
        for (j=0 ; j        {
            scanf("%s", string);
            if (1 == check)
                continue;
            check = check_prefix(&string[0]);
        }
        if (1 == check)
            printf("NO\n");
        else
            printf("YES\n");
    }
}