糯米

TI DaVinci, gstreamer, ffmpeg
随笔 - 167, 文章 - 0, 评论 - 47, 引用 - 0
数据加载中……

POJ 1432 Decoding Morse Sequences 动态规划+hash

思路如下:

匹配的递归过程如下。
把单词和正文都转换成mos码来表示。
从正文的头部开始匹配。
如果某个单词是正文的前缀,那么从前缀后面的部分递归下去。
统计一下所有方案的数目,就是答案了。
子问题就是“从位置k开始匹配,有多少种方案”,数组保存即可。

关键在于怎样快速发现某个单词是正文的前缀。
如果顺序查找,复杂度O(N),超时。
如果枚举单词长度后二分查找,复杂度O(L*lgN),应该不会超时,但代码不太自然,比较难写。
如果枚举单词长度后用hash查找,复杂度O(L),不会超时,而且代码比较好写。

事实证明,经典的字符串hash函数同样可以用于mos码,在65536格的闭hash里面没有产生冲突!

#include <stdio.h>
#include 
<string.h>
#include 
<stdlib.h>

char *mos[] = {
    
".-",
    
"-",
    
"-.-.",
    
"-..",

    
".",
    
"..-.",
    
"--.",
    
".",

    
"..",
    
".---",
    
"-.-",
    
".-..",

    
"--",
    
"-.",
    
"---",
    
".--.",

    
"--.-",
    
".-.",
    
"",
    
"-",

    
"..-",
    
"-",
    
".--",
    
"-..-",

    
"-.--",
    
"--..",
};

#define HASH_SIZE 65536
#define INPUT_LEN 10032

struct _hash {
    
int val, cnt;
};

struct _hash hash[HASH_SIZE];
int dp[INPUT_LEN];
int max_len;

int strhash(char *str, int len)
{
    
int val;
    
for (val = 0; len--; str++)
        val 
= val*31 + *str;
    
return val & 0x7fffffff;
}

struct _hash *find(int val)
{
    
int h;

    
for (h = val % HASH_SIZE;
         hash[h].cnt 
&& hash[h].val != val;
         h 
= (h + 1% HASH_SIZE
        );
    
return &hash[h];
}

void insert(char *str)
{
    
int len = strlen(str);
    
int val = strhash(str, len);
    
struct _hash *= find(val);

//    printf("insert %s\n", str);

    
if (len > max_len)
        max_len 
= len;

    h
->val = val;
    h
->cnt++;
}

int calc(char *str, int start)
{
    
struct _hash *h;
    
int i, s;

//    printf("start %d %s\n", start, str + start);

    
if (!str[start])
        
return 1;

    
if (dp[start] != -1)
        
return dp[start];

    s 
= 0;
    
for (i = 1; str[start + i - 1&& i <= max_len; i++) {
        h 
= find(strhash(str + start, i));
//        printf("len %d %s cnt %d\n", i, str + start, h->cnt);
        if (h->cnt)
            s 
+= calc(str, start + i) * h->cnt;
    }

    dp[start] 
= s;
    
return s;
}

void solve()
{
    
int i, j, d, n;
    
static char word[32], str[256], in[10032];

    memset(dp, 
-1sizeof(dp));
    memset(hash, 
0sizeof(hash));
    
    scanf(
"%s%d"in&n);
    
for (i = 0; i < n; i++) {
        scanf(
"%s", word);
        str[
0= 0;
        
for (j = 0; word[j]; j++)
            strcat(str, mos[word[j] 
- 'A']);
        insert(str);
    }
//    printf("max_len %d\n", max_len);
    printf("%d\n", calc(in0));
}

int main()
{
    
int d;

    scanf(
"%d"&d);
    
while (d--)
        solve();

    
return 0;
}

posted on 2010-07-21 14:27 糯米 阅读(686) 评论(0)  编辑 收藏 引用 所属分类: POJ


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理