NC50357. 最短母串
描述
给定n个字符串
，要求找到一个最短的字符串T，使得这n个字符串都是T的子串。
输入描述
第一行是一个正整数n，表示给定的字符串的个数；
以下的n行，每行有一个全由大写字母组成的字符串。
输出描述
只有一行，为找到的最短的字符串T。
在保证最短的前提下，如果有多个字符串都满足要求，那么必须输出按字典序排列的第一个。
示例1
输入:
2 ABCD BCDABC
输出:
ABCDABC
NC50357. 最短母串
描述
输入描述
第一行是一个正整数n，表示给定的字符串的个数；
以下的n行，每行有一个全由大写字母组成的字符串。
输出描述
只有一行，为找到的最短的字符串T。
在保证最短的前提下，如果有多个字符串都满足要求，那么必须输出按字典序排列的第一个。
示例1
输入:
2 ABCD BCDABC
输出:
ABCDABC
Java(javac 1.8) 解法, 执行用时: 1678ms, 内存消耗: 148772K, 提交时间: 2021-03-08 14:25:00
import java.io.*;
import java.lang.reflect.Type;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.text.DecimalFormat;
import java.util.*;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.Future;
import java.util.concurrent.FutureTask;
import java.util.concurrent.locks.LockSupport;
public class Main {
static class Task {
public int[] tn(int a){
int f[] = new int[11];
if(a==0) {
return new int[2];
}
int p = 1;
while(a>0){
int w = a%10;
f[p++] = w;
a/=10;
}
return Arrays.copyOf(f,p);
}
public int[] tt(String a){
int f[] = new int[2010];
int p = 1;
for(int i=a.length()-1;i>=0;--i) {
f[p++] = a.charAt(i)-'0';
}
return Arrays.copyOf(f, p);
}
static int rt = 0;
static int ch[][] ;
static int fa[];
static int id[];
static int mk[];
static int ct = 1;
static int cnt[];
static void insert(String s,int j,int num) {
int p = 0; // root
for (char c : s.toCharArray()) {
int d = c - 'A';
if (ch[p][d] == 0) {
ch[p][d] = ct++;
}
p = ch[p][d];
// mk[p]+= num;
}
mk[p] |= 1 << j;
// id[p] = 1 << j;
}
static int q[] ;
static int q1[] ;
static void build(){
int s = 0; int e = 0;
for(int i=0;i<26;++i) {
if(ch[0][i]>0) {
q[e++] = ch[0][i];
}
}
while(s<e){
int c = q[s++];
// if(id[fa[c]]>0){
// id[c] = id[fa[c]];
// }
mk[c] |= mk[fa[c]];
for(int j=0;j<26;++j){
if(ch[c][j]>0){
fa[ch[c][j]] = ch[fa[c]][j];
q[e++] = ch[c][j];
}else{
ch[c][j] = ch[fa[c]][j];
}
}
}
// for(int i=e-1;i>=0;--i){
// if(id[q[i]]!=-1){
// cnt[id[q[i]]] += mk[q[i]];
// }
// mk[fa[q[i]]] += mk[q[i]];
// }
}
static int search(String s){
int at = 0;
int cnt = 0;
for(char c:s.toCharArray()){
int to = c-'a';
to = ch[at][to];
int j = to;
while(j != 0) {
cnt += mk[to];
j = fa[j];
}
}
return cnt;
}
public void solve(int testNumber, InputReader in, PrintWriter out) {
int t = 1;
for(int i=0;i<t;++i){
int n = in.nextInt();
rt = 0;
ct = 1;
cnt = new int[n];
String s[] = new String[n];
int tot = 0;
for(int j=0;j<n;++j){
s[j] = in.next();
tot += s[j].length();
}
q = new int[(tot+1)*(1<<n)];
q1 = new int[(tot+1)*(1<<n)];
ch = new int[tot+1][26];
fa = new int[tot+1];
mk = new int[tot+1];
// id = new int[tot+1];
// Arrays.fill(id,-1);
for(int j=0;j<n;++j){
insert(s[j], j, 1);
}
build();
int e = 0;
int st = 0;
int dp[][] = new int[1<<n][ct];
for(int u[]:dp){
Arrays.fill(u,100000);
}
int fdp[][][] = new int[1<<n][ct][3];
q[e] = 0;
q1[e] = 0; e++;
dp[0][0] = 0;
ut:while(st<e){
int cst = q1[st];
int at = q[st++];
for(int j=0;j<26;++j){
int nxt = ch[at][j];
int nst = cst|mk[nxt];
if(dp[nst][nxt]> dp[cst][at]+1){
dp[nst][nxt] = dp[cst][at] + 1;
fdp[nst][nxt] = new int[]{cst,at,j};
q[e] = nxt;
q1[e++] = nst;
if(nst==(1<<n)-1){
break ut;
}
}
}
}
int fi = q1[e-1];
int pt = q[e-1];
char cs[] = new char[dp[fi][pt]];
int p = cs.length-1;
while(p!=-1){
int u[] = fdp[fi][pt];
fi = u[0];
pt = u[1];
cs[p--] = (char)('A'+u[2]);
}
out.println(new String(cs));
}
}
static long mul(long a, long b, long p) {
long res = 0, base = a;
while (b > 0) {
if ((b & 1L) > 0)
res = (res + base) % p;
base = (base + base) % p;
b >>= 1;
}
return res;
}
static long mod_pow(long k, long n, long p) {
long res = 1L;
long temp = k % p;
while (n != 0L) {
if ((n & 1L) == 1L) {
res = mul(res, temp, p);
}
temp = mul(temp, temp, p);
n = n >> 1L;
}
return res % p;
}
public static double roundD(double result, int scale) {
BigDecimal bg = new BigDecimal(result).setScale(scale, RoundingMode.UP);
return bg.doubleValue();
}
}
private static void solve() {
InputStream inputStream = System.in;
// InputStream inputStream = null;
// try {
// inputStream = new FileInputStream(new File("D:\\chrome_download\\exp.out"));
// } catch (FileNotFoundException e) {
// e.printStackTrace();
// }
OutputStream outputStream = System.out;
// OutputStream outputStream = null;
// File f = new File("D:\\chrome_download\\");
// try {
// f.createNewFile();
// } catch (IOException e) {
// e.printStackTrace();
// }
// try {
// outputStream = new FileOutputStream(f);
// } catch (FileNotFoundException e) {
// e.printStackTrace();
// }
InputReader in = new InputReader(inputStream);
PrintWriter out = new PrintWriter(outputStream);
Task task = new Task();
task.solve(1, in, out);
out.close();
}
public static void main(String[] args) {
new Thread(null, () -> solve(), "1", (1 << 30)).start();
// solve();
}
static class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String nextLine() {
String line = null;
try {
line = reader.readLine();
} catch (IOException e) {
throw new RuntimeException(e);
}
return line;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
public char nextChar() {
return next().charAt(0);
}
public int[] nextArray(int n) {
int res[] = new int[n];
for (int i = 0; i < n; ++i) {
res[i] = nextInt();
}
return res;
}
public long nextLong() {
return Long.parseLong(next());
}
public double nextDouble() {
return Double.parseDouble(next());
}
}
}
C++14(g++5.4) 解法, 执行用时: 646ms, 内存消耗: 38932K, 提交时间: 2019-12-13 00:58:56
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1024;
struct Node {
int ch[26];
int fail;
int val;
};
Node nodes[MAXN];
int sz;
void insert(string s, int idx) {
int cur = 0;
for (auto ch: s) {
int id = ch - 'A';
int &nxt = nodes[cur].ch[id];
if (nxt == 0) nxt = ++sz;
cur = nxt;
}
nodes[cur].val |= 1<<idx;
}
void build() {
queue<int> Q; Q.push(0);
while (!Q.empty()) {
auto s = Q.front(); Q.pop();
for (int i = 0; i < 26; i++) {
int &t = nodes[s].ch[i];
int f = nodes[s].fail;
if (t == 0) t = nodes[f].ch[i];
else {
// cout << s << " " << i << endl;
while (f && !nodes[f].ch[i]) f = nodes[f].fail;
nodes[t].fail = !s?0: nodes[f].ch[i];
Q.push(t);
}
}
}
}
int vis[1024][1<<12];
int cnt[1024][1<<12];
int last1[1024][1<<12];
int last2[1024][1<<12];
int main() {
int n; cin >> n;
vector<string> S(n); for (auto &s: S) cin >> s;
for (int i = 0; i < n; i++) insert(S[i], i);
build();
memset(cnt, 0x3f, sizeof(cnt));
queue<pair<int, int>> Q;
Q.push({0, 0});
cnt[0][0] = 0;
vis[0][0] = true;
while (!Q.empty()) {
auto s = Q.front().first;
auto m = Q.front().second;
// cout << s << " " << m << endl;
Q.pop();
for (int i = 0; i < 26; i++) {
int t = nodes[s].ch[i];
int tm = m;
while (true) {
tm |= nodes[t].val;
if (!vis[t][tm]) {
Q.push({t, tm});
vis[t][tm] = i + 'A';
cnt[t][tm] = cnt[s][m] + 1;
last1[t][tm] = s;
last2[t][tm] = m;
}
if (t == 0) break;
t = nodes[t].fail;
}
}
}
int best = 0x3f3f3f3f;
int last_i = 0;
int ma = (1<<n)-1;
for (int i = 0; i <= sz; i++) {
if (best > cnt[i][ma]) {
best = cnt[i][ma];
last_i = i;
}
}
// cout << last_i << " " << best << endl;
string ans;
while (last_i != 0 || ma != 0) {
ans.push_back(vis[last_i][ma]);
tie(last_i, ma) = tie(last1[last_i][ma], last2[last_i][ma]);
}
reverse(ans.begin(), ans.end());
cout << ans << endl;
}
C++ 解法, 执行用时: 92ms, 内存消耗: 13600K, 提交时间: 2021-07-21 11:29:59
#include<bits/stdc++.h>
using namespace std;
const int N=610,M=5000;
int n,cnt,tot,num,tim,ch[N][26],fail[N],st[N],a[N],ans[N*M],fa[N*M];
bool vis[N][M];
char str[N];
void build()
{
queue<int>q;
for(int i=0;i<26;i++)if(ch[0][i])q.push(ch[0][i]);
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=0;i<26;i++)
if(ch[u][i])
{
fail[ch[u][i]]=ch[fail[u]][i];
st[ch[u][i]]|=st[ch[fail[u]][i]];
q.push(ch[u][i]);
}
else ch[u][i]=ch[fail[u]][i];
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%s",str);
int u=0,len=strlen(str);
for(int j=0;j<len;j++)
{
if(!ch[u][str[j]-'A'])ch[u][str[j]-'A']=++cnt;
u=ch[u][str[j]-'A'];
}
st[u]|=1<<i-1;
}
build();
queue<int>q1,q2;
q1.push(0),q2.push(0);
while(!q1.empty())
{
int u=q1.front(),S=q2.front();
q1.pop(),q2.pop();
if(S==(1<<n)-1)
{
while(tim)a[++num]=ans[tim],tim=fa[tim];
for(int i=num;i;i--)printf("%c",a[i]+'A');
return 0;
}
for(int i=0;i<26;i++)
if(!vis[ch[u][i]][S|st[ch[u][i]]])
{
vis[ch[u][i]][S|st[ch[u][i]]]=1;
q1.push(ch[u][i]),q2.push(S|st[ch[u][i]]);
fa[++tot]=tim,ans[tot]=i;
}
tim++;
}
}