AtCoder ABC #343 : G - Compress Strings

なんか同じのどこかで見たことある気もする。
https://atcoder.jp/contests/abc343/tasks/abc343_g

問題

N個の文字列が与えられる。
それぞれを部分文字列として含む最短の文字列長を求めよ。

解法

下記で既出。
LeetCode Weekly Contest 111 : 943. Find the Shortest Superstring - kmjp's blog

ただ、上のLeetCodeの場合は文字列長が短いため、片方の文字列のsuffixともう片方の文字列のprefixの重複部分を総当たりで求めている。
以下は、そこをZ-Algorithmで高速化している。

int N;
string S[22];
int L[22];
int dp[1<<20][20];

int ig[20],im;
int C[20][20];

using VT = string;

vector<int> Zalgo(VT s) {
	vector<int> v(1,s.size());
	for(int i=1,l=-1,r=-1;i<s.size();i++) {
		if(i<=r && v[i-l]<r-i+1) v.push_back(v[i-l]);
		else {
			l=i; r=(i>r)?i:(r+1);
			while(r<s.size() && s[r-i]==s[r]) r++;
			v.push_back((r--)-l);
		}
	}
	v.push_back(0);
	return v;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	int mask;
	FOR(mask,1<<N) FOR(i,N) dp[mask][i]=1<<30;
	
	FOR(i,N) {
		cin>>S[i];
		L[i]=S[i].size();
	}
	FOR(x,N) FOR(y,N) if(x!=y) {
		string V=S[y]+S[x];
		auto Z=Zalgo(V);
		C[x][y]=L[y];
		
		if(S[x]==S[y]) {
			if(x<y) {
				ig[x]++;
				im|=1<<x;
			}
			continue;
		}
		
		FOR(i,L[x]) {
			if(Z[L[y]+i]+L[y]+i==L[x]+L[y]) chmin(C[x][y],L[y]-(L[x]-i));
			if(Z[L[y]+i]>=L[y]) {
				ig[y]++;
				im|=1<<y;
			}
		}
	}
	
	FOR(i,N) if(ig[i]==0) dp[(1<<i)^im][i]=L[i];
	int mi=1<<30;
	FOR(mask,1<<N) FOR(i,N) if(dp[mask][i]<1<<30) {
		FOR(x,N) if((mask&(1<<x))==0) chmin(dp[mask|(1<<x)][x],dp[mask][i]+C[i][x]);
		if(mask==(1<<N)-1) mi=min(mi,dp[mask][i]);
	}
	cout<<mi<<endl;
	
}

まとめ

どっかで見たと思ったらまさかのLeetCodeだったか。
ただ、LeetCodeで見たときもすでに「過去に見たことある」って感想書いてるな。