Chinaunix首页 | 论坛 | 博客
  • 博客访问: 2406792
  • 博文数量: 392
  • 博客积分: 7040
  • 博客等级: 少将
  • 技术积分: 4138
  • 用 户 组: 普通用户
  • 注册时间: 2009-06-17 13:03
个人简介

范德萨发而为

文章分类

全部博文(392)

文章存档

2017年(5)

2016年(19)

2015年(34)

2014年(14)

2013年(47)

2012年(40)

2011年(51)

2010年(137)

2009年(45)

分类:

2009-12-25 13:57:17

Hard problem
Submit: 590   Accepted:156
Time Limit: 4000MS  Memory Limit: 200000K
Description
小明在读小学的时候实在是很贪玩,常常旷课跑出去玩,最后终于被老师给逮着了。老师可不会那么轻易地放过他,他得想个法子改改小明这坏习惯。刚好,老师知 道小明的数学不好,然后想给他提高提高,怎么办呢?那就数数吧,老师也是个懂点电脑的人,他为了折腾小明,他随机生成了一个大串,然后叫小明去统计里边一 些子串出现的次数,但是他怕小明眼花,所以字串的长度都不会超过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));
        }
    }
}
阅读(789) | 评论(2) | 转发(0) |
给主人留下些什么吧!~~

jiangwen1272010-08-04 09:35:46

这里用二维数组来实现trie,length指向当前可用的数组行号,这个length在每出现 一个新字串时会向下增长

chinaunix网友2010-07-06 02:03:53

你好,我想问一下创建字典树函数中,length是做什么用的?我看不太懂,麻烦你能不能解释一下?谢谢