字符串匹配 boj1302

Hard problemSubmit: 590   Accepted:156Time Limit: 4000MS  Memory Limit: 200000KDescription
小明在读小学的时候实在是很贪玩，常常旷课跑出去玩，最后终于被老师给逮着了。老师可不会那么轻易地放过他，他得想个法子改改小明这坏习惯。刚好，老师知 道小明的数学不好，然后想给他提高提高，怎么办呢？那就数数吧，老师也是个懂点电脑的人，他为了折腾小明，他随机生成了一个大串，然后叫小明去统计里边一 些子串出现的次数，但是他怕小明眼花，所以字串的长度都不会超过8，但是取而代之的是会有大量的子串，当然子串可以有部分重叠。但是小明也不是一个笨小 孩，他知道这些事情要他自己干的话也就十来二十年吧，不算太多，那也不少，所以他想请求在座的计算机大牛们帮帮他吧。
给一个由小写字母组成的字符串S 长度1<=L<=2^14 再给Q＜200000次查询，每次查询都是一个字符串s长度1<=l<=8，要求找出给出的字符串s在S中出现的次数。


Input
多组数据测试
输入由3部分组成:
第一行为字符串S（字符串均由小写字母组成)
第二行为查询次数Q,
接下来为Q 行每行一个字符串.


Output
对应于每个查询的字符串输出此字符串在原字符串S中出现的次数.


Sample Input

ababababab
3
ab
aba
bab
accsafdac
1
ac


Sample Output

Case 1:
5
4
4
Case 2:
2

解题思路：
常见的字符串匹配，注意题目的要求，一个串会有多次匹配查询，所有适合先对原字符串建trie。每个查询串最多长8个字符，所以在建trie时只选择建长度为<8的串，在trie的每个位置都有一个count记录到达该位置的串的个数，匹配的时候只要把该位置的count提取出来就行

还是用二维数组来实现的trie
#include 
#include 

typedef struct _node
{
    int next;
    int count;
}ST_NODE;

ST_NODE trie[160000][26];
int length;
char string[20000];

void trie_build(char *string)
{
    char *ch;
    int i, next, start, length = 0;
    /* build all substring in trie */
    while ('\0' != *string)
    {
        ch = string;
        start = 0;
        for (i=0 ; i<8 ; i++, ch++)
        {
            if ('\0' == *ch)
                break;
            next = *ch - 'a';
            if (0 == trie[start][next].next)
                trie[start][next].next = ++length;
            trie[start][next].count++;
            start = trie[start][next].next;
        }
        string++;
    }
}

int trie_search(char *query)
{
    int next, start = 0, count;
    while ('\0' != *query)
    {
        next = *query - 'a';
        if (0 == trie[start][next].next)
            break;
        count = trie[start][next].count;
        start = trie[start][next].next;
        query++;
    }
    if ('\0' != *query)
        return 0;
    else
        return count;
}

int main(int argc, char *argv[])
{
    int Q, i, j = 1;
    char query[10];
    while (EOF != scanf("%s", string))
    {
        memset(trie, 0, sizeof(trie));
        trie_build(string);
        scanf("%d", &Q);
        printf("Case %d:\n", j++);
        for (i=0 ; i        {
            scanf("%s", query);
            printf("%d\n", trie_search(query));
        }
    }
}