正题

题目链接:https://www.luogu.com.cn/problem/CF25E

题目大意

给出三个串，然后求一个最短的串包含这三个串。

\(1\leq |s_1|,|s_2|,|s_3|\leq 10^5\)

解题思路

把三个串状压，先跑出\(AC\)自动机和每个节点包含的串的状态。

然后设\(f_{i,s}\)表示目前到节点\(i\)，已经包含串的状态是\(s\)，然后\(bfs\)转移即可。

时间复杂度\(O(2^3\sum |s|)\)

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#define p(x,y) (((x)*n)+(y))

using namespace std;

const int N=3e5+10;

struct node{

	int to,next;

}a[N*3*26];

int n,t[N][26],k[N],fail[N];

int tot,ls[N<<3],dis[N<<3];

char s[N];

queue<int> q;

void addl(int x,int y){

	a[++tot].to=y;

	a[tot].next=ls[x];

	ls[x]=tot;return;

}

int Insert(char *s){

	int x=0,l=strlen(s);

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

		int c=s[i]-'a';

		if(!t[x][c])t[x][c]=n++;

		x=t[x][c];

	}

	return x;

}

void GetFail(){

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

 		if(t[0][i])q.push(t[0][i]);

	while(!q.empty()){

		int x=q.front();q.pop();

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

			if(t[x][i]){

				fail[t[x][i]]=t[fail[x]][i];

				q.push(t[x][i]);

			}

			else t[x][i]=t[fail[x]][i];

		}

		k[x]|=k[fail[x]];

	}

	return;

}

int bfs(){

	q.push(0);dis[0]=1;

	while(!q.empty()){

		int x=q.front();q.pop();

		for(int i=ls[x];i;i=a[i].next){

			int y=a[i].to;

			if(dis[y])continue;

			dis[y]=dis[x]+1;

			if(y/n==7)return dis[y]-1;

			q.push(y);

		}

	}

	return 0;

}

int main()

{

	n=1;

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

		scanf("%s",s);

		k[Insert(s)]|=(1<<i);

	}

	GetFail();

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

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

			int y=t[x][i];

			if(!y)continue;

			for(int s=0;s<7;s++)

				addl(p(s,x),p(s|k[y],y));

		}

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

	return 0;

}

巴特西

CF25E-Test【AC自动机,bfs】

正题

题目大意

解题思路

code

最新文章

热门文章