hdu 2846 字典树变形

mark: 题目有字串匹配的过程 有两点

1.为了高效的匹配子串 可以把所有的子串都预处理进去 然后字典树计数就放在最后面

2.在同一个母串处理自串的时候 会有重复的时候 比如abab  这里去重用个标记位就可以了（一开始用map 结果超时了，，，  果然还是想太简单了）

上代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<string>
#define maxn 27
using namespace std;
struct Tri
{
    int num,id;
    Tri*next[maxn];
    Tri()
    {
        num=0,id=0;
        memset(next,0,sizeof(next));
    }
};
void buildTri(Tri*root,string str,int ret)
{
    for(int i=0;i<str.size();i++)
    {
        int id=str[i]-'a';
        if(root->next[id]==NULL) root->next[id]=new Tri();
        root=root->next[id];
    }
    if(root->id!=ret) root->num++,root->id=ret;//  序号不一样的时候 计数 然后标记更新
}
int findTri(Tri *root,string str)
{
    for(int i=0;i<str.size();i++)
    {
        int id=str[i]-'a';
        if(root->next[id]==NULL) return 0;
        root=root->next[id];
    }
    return root->num;
}
int main()
{
    cin.sync_with_stdio(false);
    int t;
    string ss;
    cin>>t;
    Tri *root=new Tri();//
    for(int ii=1;ii<=t;ii++)
    {
        cin>>ss;
        int len=ss.size();
        string zz;
        map<string,int> fuck;
        for(int i=0;i<ss.size();i++)// 预处理过程 将所有的字串都放进去
        {
            for(int j=1;j<=ss.size()-i;j++)
            {
                zz=ss.substr(i,j);
                buildTri(root,zz,ii);
            }
        }
    }
    cin>>t;
    while(t--)
    {
        cin>>ss;
        cout<<findTri(root,ss)<<endl;
    }
    return 0;
}