• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            糯米

            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 糯米 閱讀(589) 評論(0)  編輯 收藏 引用 所屬分類: POJ

            久久亚洲国产精品一区二区| 久久久久亚洲精品男人的天堂 | 久久夜色精品国产亚洲| 久久久国产精品亚洲一区| 久久精品成人免费看| 久久久久国产| 久久午夜无码鲁丝片| 国产成人香蕉久久久久| 久久亚洲熟女cc98cm| 亚洲一本综合久久| 久久亚洲AV无码精品色午夜麻豆| 精品久久久久久亚洲精品| 久久毛片免费看一区二区三区| 亚洲αv久久久噜噜噜噜噜| 久久精品成人| 国产精品久久久久久吹潮| 中文字幕亚洲综合久久菠萝蜜| 国产精品久久久久无码av| 免费精品久久天干天干| 久久精品成人欧美大片| 久久99国产综合精品免费| 久久婷婷五月综合国产尤物app| 久久综合综合久久97色| AV色综合久久天堂AV色综合在| 人妻无码精品久久亚瑟影视| 狠狠色丁香婷婷久久综合不卡| 久久久无码精品亚洲日韩蜜臀浪潮 | .精品久久久麻豆国产精品 | 亚洲国产精品久久久久婷婷软件 | 精品久久亚洲中文无码| 久久无码精品一区二区三区| 亚洲欧美日韩精品久久| av无码久久久久久不卡网站 | 久久精品一区二区三区中文字幕 | 久久久中文字幕| 国产精品久久久久国产A级| 亚洲中文字幕久久精品无码喷水| 人妻无码精品久久亚瑟影视 | 精品少妇人妻av无码久久| av色综合久久天堂av色综合在| 无码人妻久久一区二区三区蜜桃 |