[POI 2000] 公共串

[题目链接]

https://www.lydsy.com/JudgeOnline/problem.php?id=2946

[算法]

建立多串后缀树

对于后缀树上的每个点 ， 判断该节点所代表的等价类是否在所以字符串中出现 ， 用该点的深度更新答案

时间复杂度 : O(NL)

[代码]

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

const int N = 1e5 + ;

const int ALPHA = ;

int n , ans;

char s[N];

template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); }

template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); }

template <typename T> inline void read(T &x)

{

    T f = ; x = ;

    char c = getchar();

    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;

    for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';

    x *= f;

}

struct Suffix_Automaton

{

        int sz , last;

        int father[N] , child[N][ALPHA] , depth[N];

        bool lab[N][];

        vector< int > a[N];

        Suffix_Automaton()

        {

                sz = ;

                last = ;

        }

        inline int new_node(int dep)

        {

                depth[++sz] = dep;

                father[sz] = ;

                memset(child[sz] ,  , sizeof(child[sz]));

                memset(lab[sz] ,  , sizeof(lab[sz]));

                return sz;

        }

        inline void extend(int ch , int c)

      {

        int np = child[last][ch];

        if (np)

        {

            if (depth[np] == depth[last] + )

            {

                lab[np][c] = true;

                last = np;

            } else

            {

                int nq = new_node(depth[last] + );

                father[nq] = father[np];

                father[np] = nq;

                memcpy(child[nq] , child[np] , sizeof(child[nq]));

                for (int p = last; child[p][ch] == np; p = father[p])

                        child[p][ch] = nq;

                lab[nq][c] = true;

                last = nq;

            }

        } else

        {

              int np = new_node(depth[last] + );

              int p = last;

              while (child[p][ch] == )

              {

                  child[p][ch] = np;

                  p = father[p];

              }

              if (child[p][ch] == np)

              {

                  father[np] = ;

                  lab[np][c] = true;

                  last = np;

                  return;

              }

              int q = child[p][ch];

              if (depth[q] == depth[p] + )

              {

                  father[np] = q;

                  lab[np][c] = true;

                  last = np;

                  return;

              } else

              {

                  int nq = new_node(depth[p] + );

                  father[nq] = father[q];

                  father[np] = father[q] = nq;

                  memcpy(child[nq] , child[q] , sizeof(child[q]));

                  while (child[p][ch] == q)

                  {

                      child[p][ch] = nq;

                      p = father[p];

                  }

                  lab[np][c] = true;

                  last = np;

                  return;

              }

        }

         }

        inline void insert(char *s , int col)

        {

                last = ;

                for (int i = ; i <= strlen(s + ); ++i)

                        extend(s[i] - 'a' , col);

        }

        inline void dfs(int u)

        {

                for (unsigned i = ; i < a[u].size(); ++i)

                {

                        int v = a[u][i];

                        dfs(v);

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

                                lab[u][j] |= lab[v][j];

                }

                bool all = true;

                for (int i = ; i <= n; ++i) all &= lab[u][i];

                if (all) chkmax(ans , depth[u]);

        }

        inline void work()

        {

                for (int i = ; i <= sz; ++i)

                        a[father[i]].push_back(i);

                dfs();

        }

} SAM;

int main()

{

        read(n);

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

        {

                scanf("%s" , s + );

                SAM.insert(s , i);

        }

        SAM.work();

        printf("%d\n" , ans);

        return ;

}