Longest Common Substring

\[ Time Limit: 294ms \quad Memory Limit: 1572864 kB \]

题意

给出两个串，求两个串的最长公共连续子序列的长度，两个串的长度小于等于250000。

思路

先对第一个串构建后缀自动机，根据后缀自动机的性质，从 \(root\) 的所有路径都是原串中的子串，又因为构建的时候，我们用 \(node[i].len\) 表示与节点 \(i\) 的 \(endpos\) 相同的所有子串集合的最长长度，那么我们就可以在后缀自动机上一次添加一个字符的去查询 \(res\) ，然后最大的 \(res\) 就是最后的答案。

在后缀自动机上查询的时候，我们用两个变量来更新答案，\(p\) 表示现在在后缀自动机上的状态，\(res\) 表示目前的最长公共连续长度。

如果对于下一个字符 \(k\) ，现在的 \(p\) 有这样的一条边，那么直接更新 \(p\)，并且 \(res\)++。

如果没有这样的一条边，那么就从 \(p\) 跳到 \(node[i].fa\) 的位置，一直跳到有 \(k\) 的一条边为止停下或者走完整个后缀自动机。

如果跳到结束也没有找到 \(k\) 边，那么就让 \(p\) 变回 \(root\)，\(res=0\)。

#include #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #define lowbit(x) x & (-x)#define mes(a, b) memset(a, b, sizeof a)#define fi first#define se second#define pii pair
                    
                     #define INOPEN freopen("in.txt", "r", stdin)#define OUTOPEN freopen("out.txt", "w", stdout)typedef unsigned long long int ull;typedef long long int ll;const int maxn = 3e5 + 10;const int maxm = 1e5 + 10;const ll mod = 1e9 + 7;const ll INF = 1e18 + 100;const int inf = 0x3f3f3f3f;const double pi = acos(-1.0);const double eps = 1e-8;using namespace std;int n, m;int cas, tol, T;struct SAM { struct Node{ int next[27]; int fa, len; void init() { mes(next, 0); fa = len = 0; } } node[maxn<<1]; int sz, last; void init() { sz = last = 1; node[sz].init(); } void insert(int k) { int p = last, np = last = ++sz; node[np].init(); node[np].len = node[p].len+1; for(; p && !node[p].next[k]; p=node[p].fa) node[p].next[k] = np; if(p==0) { node[np].fa = 1; } else { int q = node[p].next[k]; if(node[q].len == node[p].len + 1) { node[np].fa = q; } else { int nq = ++sz; node[nq] = node[q]; node[nq].len = node[p].len+1; node[np].fa = node[q].fa = nq; for(; p&&node[p].next[k]==q; p=node[p].fa) node[p].next[k] = nq; } } } int solve(char *s) { int len = strlen(s+1); int res = 0, p = 1, ans = 0; for(int i=1; i<=len; i++) { int k = s[i]-'a'+1; while(p && !node[p].next[k]) { p = node[p].fa; res = node[p].len; } if(!p) { p = 1; res = 0; } else { p = node[p].next[k]; res++; } ans = max(ans, res); } return ans; }} sam;char s[maxn], t[maxn];int main() { scanf("%s%s", s+1, t+1); sam.init(); int len = strlen(s+1); for(int i=1; i<=len; i++) { sam.insert(s[i]-'a'+1); } int ans = sam.solve(t); printf("%d\n", ans); return 0;}

转载于:https://www.cnblogs.com/Jiaaaaaaaqi/p/10897550.html

你可能感兴趣的文章