Longest Common Substring II

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

题意

给出\(n\)个子串，要求这\(n\)个子串的最长连续公共子串长度。

思路

前置技能：当 \(n=2\) 时的做法，可以先做做这题：SPOJ-LCS，我的博客：SPOJ-LCS题解

这里为了方便，我们定义 \(LCS\) 为题中所求的最长连续公共子串。
当 \(n>2\) 时，我们可以对第一个串构建后缀自动机，然后用上一题一样的做法，求出后缀自动机上每个节点和当前串的 \(LCS\) ，用 \(tmplen[i]\) 数组来保存。那么当前节点对于所有串的 \(LCS\) 就是每一个串的 \(tmplen[i]\) 的最小值，用 \(anslen[i]\) 来表示。

对于一个串，求出 \(tmplen[i]\) 是很好求的，在每次更新的时候加上一句话就可以了

tmplen[p] = max(tmplen[p], res);

但是这样会不会漏情况？答案是会的！我们现在只找到了当前串的在 \(p\) 节点的 \(LCS\) ，但是对于 \(p\) 的 \(father\) 那些节点，是不是也会匹配上，只是长度更小而已？

当 \(n=2\) 的时候，不往 \(father\) 上更新，由于长度更短，所以并不会影响最终的答案。
当 \(n>2\) 的时候，这时候 \(tmplen[father]\) 虽然不会影响当前串的答案，但是它却会影响到全部串的 \(anslen[father]\) ，也就是说虽然 \(father\) 这个节点在当前串中不是最优答案，但他却可能是全部串的最优答案，所以我们需要将 \(tmplen[i]\) 往 \(tmplen[father]\) 上更新。

那么要怎么更新呢？

想想后缀自动机的性质，我们可以发现与\(p\)匹配的串，一定也可以与\(node[p].fa\)匹配上，又由于 \(tmplen\) 的含义是当前串的 \(LCS\)，所以我们可以得到

tmplen[father] = max(tmplen[father], tmplen[p]);

但是取 \(max\) 的时候，我们又要限制不超出这个节点的总长度，进而得到

tmplen[father] = min(tmplen[father], node[father].len);

我这里比较懒，不想用基数排序，直接用 \(dfs\) 在 \(parent\) 树上更新了，也是 \(O(N)\) 的复杂度。（代码中的变量和上述有差，但思路意思是一样的）。

void dfs(int u) {

	for(auto v : vv[u]) {

		dfs(v);

		tmplen[u] = max(tmplen[u], min(tmplen[v], node[u].len));

	}

}

如此下来，我们就成功的将每一个串的 \(tmplen\) 求出来了，最后在更新一下 \(anslen\) ，最后的答案就是 \(anslen\) 中的最大值。

#include <map>

#include <set>

#include <list>

#include <ctime>

#include <cmath>

#include <stack>

#include <queue>

#include <cfloat>

#include <string>

#include <vector>

#include <cstdio>

#include <bitset>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#define  lowbit(x)  x & (-x)

#define  mes(a, b)  memset(a, b, sizeof a)

#define  fi         first

#define  se         second

#define  pii        pair<int, int>

#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 len, fa;

		void init() {

			mes(next, 0);

			fa = len = 0;

		}

	} node[maxn<<1];

	vector<int> vv[maxn<<1];

	int anslen[maxn<<1];

	int tmplen[maxn<<1];

	int sz, last;

	void init() {

		sz = last = 1;

		node[1].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;

			}

		}

	}

	void handle() {

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

			vv[i].clear();

			anslen[i] = node[i].len;

		}

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

			vv[node[i].fa].push_back(i);

		}

	}

	void dfs(int u) {

		for(auto v : vv[u]) {

			dfs(v);

			tmplen[u] = max(tmplen[u], min(tmplen[v], node[u].len));

		}

	}

	void solve(char *s) {

		mes(tmplen, 0);

		int len = strlen(s+1);

		int p = 1, res = 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==0) {

				res = 0;

				p = 1;

			} else {

				p = node[p].next[k];

				res++;

			}

			tmplen[p] = max(tmplen[p], res);

		}

		dfs(1);

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

			anslen[i] = min(anslen[i], tmplen[i]);

		}

	}

} sam;

char s[maxn];

int main() {

	sam.init();

	scanf("%s", s+1);

	int len = strlen(s+1);

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

		sam.insert(s[i]-'a'+1);

	}

	sam.handle();

	int ans = 0;

	while(~scanf("%s", s+1)) {

		sam.solve(s);

	}

	for(int i=1; i<=sam.sz; i++) {

		ans = max(ans, sam.anslen[i]);

	}

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

	return 0;

}

巴特西

Longest Common Substring II SPOJ - LCS2 （后缀自动机）

Longest Common Substring II

题意

思路

最新文章

热门文章