ACM学习历程—HDU2222 Keywords Search（字典树）

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <vector>
#define INF 0x3fffffff

using namespace std;

struct tree
{
    tree *next[26];
    int End;
    bool Endvis;
};

char s[1000005];

void Add(char *str, tree *head)
{
    char *a = str;
    tree *p = head;
    while (a[0] != ‘\0‘)
    {
        int k = a[0]-‘a‘;
        if (p->next[k] == NULL)
        {
            tree *p1;
            p1 = (tree*)malloc(sizeof(tree));
            for (int i = 0; i < 26; ++i)
            {
                p1->next[i] = NULL;
            }
            p1->End = 0;
            p1->Endvis = 0;
            p->next[k] = p1;
        }
        p = p->next[k];
        ++a;
    }
    p->End += 1;
}

int Find (char *str, tree *head)
{
    char *s = str;
    tree *p = head;
    int ans = 0;
    while (s[0] != ‘\0‘)
    {
        int k = s[0]-‘a‘;
        if (p->next[k] == NULL)
        {
            break;
        }
        else
        {
            p = p->next[k];
        }
        if (p->End > 0 && p != head)
        {
            if (p->Endvis == 0)
            {
                ans += p->End;
                p->Endvis = 1;
            }
        }
        ++s;
    }
    if (p == head) return 0;
    return ans;
}

int main()
{
    //freopen ("test.txt", "r", stdin);
    int T;
    scanf ("%d", &T);
    for (int times = 0; times < T; ++times)
    {
        tree *head;
        int n;
        head = (tree*)malloc(sizeof(tree));
        for (int i = 0; i < 26; ++i)
        {
            head->next[i] = NULL;
        }
        scanf ("%d", &n);
        for (int i = 0; i < n; ++i)
        {
            char str[55];
            scanf ("%s", str);
            if (str[0] != ‘\0‘) Add (str, head);
        }
        scanf ("%s", s);
        int len = strlen(s), ans = 0;
        for (int i = 0; i < len; ++i)
        {
            ans += Find(s+i, head);
        }
        printf ("%d\n", ans);
    }
    return 0;
}