hdu 2846 Repository 字典樹的變形

　　　　　　　　　　　Repository

　　　　　　　　　　　　Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/65536 K (Java/Others)
　　　　　　　　　　　　　　　　　　Total Submission(s): 1129????Accepted Submission(s): 382

Problem Description

When you go shopping, you can search in repository for avalible merchandises by the computers and internet. First you give the search system a name about something, then the system responds with the results. Now you are given a lot merchandise names in repository and some queries, and required to simulate the process.

Input

There is only one case. First there is an integer P (1<=P<=10000)representing the number of the merchanidse names in the repository. The next P lines each contain a string (it's length isn't beyond 20,and all the letters are lowercase).Then there is an integer Q(1<=Q<=100000) representing the number of the queries. The next Q lines each contains a string(the same limitation as foregoing descriptions) as the searching condition.

Output

For each query, you just output the number of the merchandises, whose names contain the search string as their substrings.

Sample Input

20

ad

ae

af

ag

ah

ai

aj

ak

al

ads

add

ade

adf

adg

adh

adi

adj

adk

adl

aes

5

b

a

d

ad

s

Sample Output

0

20

11

11

2

根據題意可知：題目屬于判斷字符串中是否包含子串的問題，對于一般的字典樹，用來判斷前綴，而這里不能直接這么去建樹。在建樹的時候將字符串X=X1X2....Xn的分別以X1,X2....Xn開頭的后綴子串插入到Trie樹中，如此一來就可以判斷某個字符串是否被包含在另一個字符串當中。但是這就有一個問題，比如插入了字符串abab，那么當查找字符串ab時就會重復計數，因此需要多設計一個標識以表示在插入"abab"和"ab"時時同一個字符串即可(是同一個字符串就不需要使計數器加1)，因此在Trie樹結點中多設計一個商品id來標記。id用來記錄最后一個經過此路徑上的商品編號，如果要插入的字符串編號同當前節點的編號不同，則計數器加1，并且將當前結點的編號置為要插入的字符串的編號。

/*hdu 2846 字典樹的變形 2011.10.18*/ 
#include <iostream>
#include<cstring> 
#define MAX 26
using namespace std;

typedef struct Trie_Node
{
int count;                  //記錄包含該結點的單詞個數 
     int id;                     //最后一次經過此結點的商品ID 
    Trie_Node *next[MAX];
}Trie;

void insert(Trie *root,char *s,int id)
{
    Trie *p=root;
while(*s!='\0')
    {
if(p->next[*s-'a']==NULL)
        {
            Trie *temp=(Trie *)malloc(sizeof(Trie));
for(int i=0;i<MAX;i++)
            {
                temp->next[i]=NULL;
            }
            temp->count=0;
            temp->id=-1;            //-1表示沒有商品 
            p->next[*s-'a']=temp;
        }
        p=p->next[*s-'a'];
if(p->id!=id)             //如果當前結點的商品ID不等于要插入商品的ID，則計數器count++，并且重新置ID的值 
         {
            p->id=id;
            p->count++;
        }
        s++;
    }
}


int search(Trie *root,char *s)
{
    Trie *p=root;
for(int i=0;s[i]!='\0';i++)
    {
if(p->next[s[i]-'a']==NULL)
return 0;
        p=p->next[s[i]-'a'];
    }    
return p->count;
}

int main(int argc, char *argv[])
{
int i,j;
int n,m;
char s[21];
    Trie *root=(Trie *)malloc(sizeof(Trie));
for(i=0;i<MAX;i++)
    {
        root->next[i]=NULL;
    }
    root->count=0;
    root->id=-1;
    scanf("%d",&n);
for(i=0;i<n;i++)
    {
        scanf("%s",s);
for(j=0;j<strlen(s);j++)       //將字符串X=X1X2...Xn的分別以X1,X2...Xn開頭的后綴字符串插入到Trie樹中 
         {
            insert(root,s+j,i);
        }    
    }
    scanf("%d",&m);
for(i=0;i<m;i++)
    {
        scanf("%s",s);
        printf("%d\n",search(root,s));
    }
return 0;
}

嘗試過用KMP去解決，但是查找復雜度至少為0(p*(len1+len2))，試著提交了一下，嚴重超時。