Codeforces 861D - Polycarp's phone book 【Trie树】

<题目链接>

题目大意：

输入7e4个长度为9的字符串，每个字符串中只出现0~9这几种数字，现在需要你输出每个母串中最短的特有子串。

解题分析：

利用Trie树进行公共子串的判定，因为Trie树的特性是对节点的前缀字符串进行操作，所以为了转换成对母串中任意区间的字符串进行操作，我们对母串中的所有后缀字符串建树。下面用了一个比较优秀的Trie树模板。

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 const int N = 7e4+;

 const int INF = 1e6;

 char buf[N][];

 int n,cur;

 struct Trie{

     int nxt[N*][],num[N*],time[N*];

     int root,pos;

     int newnode(){

         for(int i=;i<;i++)nxt[pos][i]=-;

         num[pos]=,time[pos]=;

         return pos++;

     }

     void init(){

         pos=;root=newnode();

     }

     void insert(char str[]){

         int len=strlen(str);

         int now=root;

         for(int i=;i<len;i++){

             int to=str[i]-'';

             if(nxt[now][to]==-)

                 nxt[now][to]=newnode();

             now=nxt[now][to];

             if(time[now]!=cur)     //建立时间戳的意义是，避免相同母串中不同位置中的相同子串产生重复标记

                 num[now]++,time[now]=cur;      //num[now]记录下含有这个子串的母串数量

         }

     }

     int query(char str[]){

         int len=strlen(str);

         int now=root;

         for(int i=;i<len;i++){

             now=nxt[now][str[i]-''];

             if(num[now]==)return i;

         }

         return -;

     }

 }trie;

 int main(){

     ios::sync_with_stdio(false);cin.tie();cout.tie();

     cin>>n;

     trie.init();

     for(int i=;i<=n;i++){

         cin>>buf[i];

         cur=i;

         for(int j=;j<;j++){

             trie.insert(buf[i]+j);     //用每个母串的所有后缀建Trie树，然后利用Trie树对前缀字符串进行操作的特性，达到对母串字符区间的操作

         }

     }

     for(int i=;i<=n;i++){

         int le=,ri=,mn=INF;

         for(int j=;j<;j++){

             int tmp=trie.query(buf[i]+j);

             if(tmp!=- && mn>tmp){      //找到每个母串中符合条件的最短子串

                 mn=tmp;le=j,ri=j+tmp;

             }

         }

         for(int j=le;j<=ri;j++)cout<<buf[i][j];

         puts("");

     }

 }

2019-02-01