糯米

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

POJ 1226 Substrings 后缀Trie

思路:

将每个字符串的原文的所有后缀和反转后的所有后缀都插入到Trie中。
同时Trie中的节点维护一个值 --- 该节点下面包含了多少个不同单词的节点。
然后统计这个值等于N的最深的节点,其深度就是答案了。
后缀Trie并不是好的解法。有人说用后缀数组也能做的,但是想不出来。


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

struct node {
    
char ch;
    
int ts, cnt;
    
struct node *sib, *child;
}
;

struct node nodes[65536], root;
int nodes_cnt;
int N, T;
int ts, ans;

inline 
struct node *insert(struct node *q, char ch, int depth)
{
    
struct node *t;

    
for (t = q->child; t; t = t->sib)
        
if (t->ch == ch)
            
break;

    
if (!t) {
        t 
= &nodes[nodes_cnt++];
        t
->ch = ch;
        t
->cnt = 0;
        t
->child = NULL;
        t
->sib = q->child;
        q
->child = t;
    }


    
if (t->ts != ts) {
        t
->ts = ts;
        t
->cnt++;
    }


    
if (t->cnt == N && depth > ans)
        ans 
= depth;

    
return t;
}


int main()
{
    
int i, j, k, len;
    
char str[128];
    
struct node *t;

    scanf(
"%d"&T);
    
while (T--{
        scanf(
"%d"&N);
        ans 
= 0;
        nodes_cnt 
= 0;
        root.child 
= root.sib = NULL;
        root.cnt 
= 0;
        
for (i = 0; i < N; i++{
            scanf(
"%s", str);
            ts
++;
            len 
= strlen(str);
            
for (j = 0; j < len; j++{
                t 
= &root;
                
for (k = j; k < len; k++)
                    t 
= insert(t, str[k], k - j + 1);
            }

            
for (j = len - 1; j >= 0; j--{
                t 
= &root;
                
for (k = j; k >= 0; k--)
                    t 
= insert(t, str[k], j - k + 1);
            }

        }

        printf(
"%d\n", ans);
    }


    
return 0;
}

posted on 2010-05-26 08:05 糯米 阅读(579) 评论(0)  编辑 收藏 引用 所属分类: POJ


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