luoguP4112 [HEOI2015]最短不公共子串

链接

思路

子串可以用后缀自动机，子序列可以用序列自动机。

序列自动机是啥，就是能访问到所有子序列的自动机。

每个点记录下一个字母最近出现的位置。不过我这里构造是\(O(n^2)\)。

然后进行bfs进行广搜就行了。

注意vis[][]剪枝，要不TLE。

代码

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N=2000+7;

int n,m;

struct node {

	int len,fa,ch[26];

}dian[4][N<<1];

int las[4]={1,1,1,1},tot[4]={1,1,1,1};

void add(int c,int who) {

	int p=las[who];int np=las[who]=++tot[who];

	dian[who][np].len=dian[who][p].len+1;

	for(;p&&!dian[who][p].ch[c];p=dian[who][p].fa) dian[who][p].ch[c]=np;

	if(!p) dian[who][np].fa=1;

	else {

	    int q=dian[who][p].ch[c];

	    if(dian[who][q].len==dian[who][p].len+1) dian[who][np].fa=q;

	    else {

	        int nq=++tot[who];

	        dian[who][nq]=dian[who][q];

	        dian[who][nq].len=dian[who][p].len+1;

	        dian[who][q].fa=dian[who][np].fa=nq;

	        for(;p&&dian[who][p].ch[c]==q;p=dian[who][p].fa)

	            dian[who][p].ch[c]=nq;

	    }

	}

}

struct edge{char s[N];}a,b;

int vis[N<<1][N<<1],flag;

void bfs(int T_T,int QwQ) {

	queue<pair<pair<int,int>,int> > q;

	q.push(make_pair(make_pair(1,1),1));

	while(!q.empty()) {

		pair<pair<int,int>,int> u=q.front();

		node lj1=dian[T_T][u.first.first],lj2=dian[QwQ][u.first.second];

		q.pop();

		for(int i=0;i<26;++i) {

			if(lj1.ch[i]&&!lj2.ch[i])

				return printf("%d\n",u.second),void();

			if(lj1.ch[i]&&lj2.ch[i]&&vis[lj1.ch[i]][lj2.ch[i]]!=flag) {

				q.push(make_pair(make_pair(lj1.ch[i],lj2.ch[i]),u.second+1));

				vis[lj1.ch[i]][lj2.ch[i]]=flag;

			}

		}

	}

	puts("-1");

}

int main() {

	scanf("%s%s",a.s,b.s);

	n=strlen(a.s),m=strlen(b.s);

	for(int i=0;i<n;++i) add(a.s[i]-'a',0);

	for(int i=0;i<m;++i) add(b.s[i]-'a',1);

	//build a

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

		if(!dian[2][1].ch[a.s[i]-'a'])

			dian[2][1].ch[a.s[i]-'a']=i+2;

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

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

			if(!dian[2][i+2].ch[a.s[j]-'a'])

				dian[2][i+2].ch[a.s[j]-'a']=j+2;

	//build b

	for(int i=0;i<m;++i)

		if(!dian[3][1].ch[b.s[i]-'a'])

			dian[3][1].ch[b.s[i]-'a']=i+2;

	for(int i=0;i<m;++i)

		for(int j=i+1;j<m;++j)

			if(!dian[3][i+2].ch[b.s[j]-'a'])

				dian[3][i+2].ch[b.s[j]-'a']=j+2;

	flag++,bfs(0,1);

	flag++,bfs(0,3);

	flag++,bfs(2,1);

	flag++,bfs(2,3);

    return 0;

}

巴特西

luoguP4112 [HEOI2015]最短不公共子串 SAM,序列自动机，广搜BFS

luoguP4112 [HEOI2015]最短不公共子串

链接

思路

代码

最新文章

热门文章