【模板】字典树

前缀树。

字符串的常用算法，后续的很多算法都是构建一颗奇奇怪怪的字典树。

Tree

在结构体树中构建节点信息，看题目要求来确定有哪些标记。如结束标记vis等等。

struct strtree
{
  bool vis=0;
  int son[30];
  int len;
}tree[N];

insert

字典树的叶子节点插入。首先我们从树的起点和字符串的起点开始。沿着树和字符串走动。

当走到某一处的时候，如果该位置没有建立过，那么就新建一个节点，并让他的父亲指向该节点。

void insert(string x)
{
  int now=0,i=0;
  while( i<s.length()-1 )
  {
    if( !tree[now].son[ x[i]-'a' ] )
    {
      tree[now].son[ x[i]-'a' ]=++cnt;
    }
    now=tree[now].son[ x[i]-'a' ];
    i++;
  }

  if( !tree[now].son[ x[i]-'a' ] )
    {
      tree[now].son[ x[i]-'a' ]=++cnt;
    }
    now=tree[now].son[ x[i]-'a' ];
    tree[now].vis=1;
}

dfs树

这部分的内容和建树的内容相差不大，主要是体现在结果的统计。

void dfs(int x)
{
  tree[x].len+=tree[x].vis;
  ans=max( ans,tree[x].len );
  for(int i=0;i<26;i++)
  {
    if( tree[x].son[i] )
    {
      tree[ tree[x].son[i] ].len=tree[x].len;
      dfs( tree[x].son[i] );
    }
  }
}

Code

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+12;
int ans=0,n,cnt;
string s;
struct strtree
{
  bool vis=0;
  int son[30];
  int len;
}tree[N];

void insert(string x)
{
  int now=0,i=0;
  while( i<s.length()-1 )
  {
    if( !tree[now].son[ x[i]-'a' ] )
    {
      tree[now].son[ x[i]-'a' ]=++cnt;
    }
    now=tree[now].son[ x[i]-'a' ];
    i++;
  }

  if( !tree[now].son[ x[i]-'a' ] )
    {
      tree[now].son[ x[i]-'a' ]=++cnt;
    }
    now=tree[now].son[ x[i]-'a' ];
    tree[now].vis=1;
}

void dfs(int x)
{
  tree[x].len+=tree[x].vis;
  ans=max( ans,tree[x].len );
  for(int i=0;i<26;i++)
  {
    if( tree[x].son[i] )
    {
      tree[ tree[x].son[i] ].len=tree[x].len;
      dfs( tree[x].son[i] );
    }
  }
}

int main(){
  cin>>n;
  while( n-- )
  {
    cin>>s;
    insert(s);
  }
  dfs(0);
  cout<<ans;
}