HDU1251 裸字典树 +HDU 2846 统计子串出现次数

HDU1251：http://acm.hdu.edu.cn/showproblem.php?pid=1251

初学字典树，码模板……

#include<iostream>
#include<string.h>
using namespace std;
char a[15];
struct node {
    node *nextt[26];
    int v=0;
};
node root;
void init()
{
    for (int i = 0; i < 26; i++)
    {
        root.nextt[i] = NULL;
    }
}
void creatree()
{
    int len = strlen(a);
    node *p = &root,*q;
    for (int i = 0; i < len; i++)
    {
        int id = a[i] - 'a';
        if (p->nextt[id] == NULL)
        {
            q = (node*)malloc(sizeof(node));
            q->v = 1;
            for (int j = 0; j < 26; j++)
                q->nextt[j] = NULL;
            p->nextt[id] = q;
            p = p->nextt[id];
        }
        else {
            p->nextt[id]->v++;
            p = p->nextt[id];
        }
    }
}
int find()
{
    int len = strlen(a);
    node *p = &root;
    for (int i = 0; i < len; i++)
    {
        int id = a[i] - 'a';
        p = p->nextt[id];
        if (p == NULL) return 0;
    }
    return p->v;
}
int main()
{
    init();
    while (gets(a) && a[0] != '')
        creatree();
    while (cin >> a)
    {
        cout << find() << endl;
    }
    return 0;
}

 HDU 2846  http://acm.hdu.edu.cn/showproblem.php?pid=2846

字典树原本是按前缀搜索的，题中所要求查询的并不一定是字符串的前缀，但我们可以将前缀转化为后缀处理，搜索子串的长度len已知，即便是不同后缀，只要搜索子串第一个后缀前len个字符即可。

orz想了好久，还是参考了大佬的题解，膜拜大佬做法，一语道破天机

#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
char a[25];
int len;
struct node {
    node *nextt[26];
    int v;
    int mark;
    node()   //加个构造函数，下面设node变量的时候就不用再初始化nextt数组了
    {
        v= 0;
        mark = -1;
        for (int i = 0; i < 26; i++)
            nextt[i] = NULL;
    }
};
node *root = new node();
void creat(int i,int j)   //j标记当前所访问的字符串
{
    node *p = root;
    for (; i < len; i++)
    {
        int id = a[i] - 'a';
        if (p->nextt[id] == NULL)
        {
            p->nextt[id]= new node();
            p = p->nextt[id];
            p->mark = j;
            p->v = 1;
        }
        else 
        {
            p = p->nextt[id];
            if (p->mark != j)    //在mark!=j的时候更新v，避免同一母串的部分前缀相同的子串多次更新，比如add
            {
                p->mark = j;
                p->v++;
            }
        }
    }
}
int find()
{
    node *p = root;
    for (int i = 0; i < len; i++)
    {
        int id = a[i] - 'a';
        if (p->nextt[id] == NULL) return 0;
        p = p->nextt[id];
    }
    return p->v;
}
int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        cin >> a;
        len = strlen(a);
        for(int i=0;i<len;i++)
        creat(i,n);
    }
    cin >> n;
    while (n--)
    {
        cin >> a;
        len = strlen(a);
        cout << find() << endl;
    }
    return 0;
}