Notations

• For a string \(T\), let \(|T|\) denote its length.
• For a string \(T\) and an non-negative integer or the infinity \(N\), denote by \(T\times N\) the string that is a \(N\)-time repetition of \(T\).
• For a string \(T\), let \(T[x:]\) denote the substring starting from the \(x\)-th character.
• Let \(\lt, \leq\) denote the lexicographical comparison of strings.
• Define \(\preceq\) by: \(X \preceq Y\) if and only if \((X+Y<Y+X)\) or \((X+Y=Y+X\) and \(X\leq Y)\). Define \(X\prec Y\) as “\(X\preceq Y\) and \(X\neq Y\).”
  • This \(\preceq\) defines a total order. That is, any two strings \(X\) and \(Y\) satisfies exactly one of \(X\prec Y\), \(Y \prec X\), and \(X=Y\). Moreover, the relation is transitive.
• Let \(T_K\) be the answer to the problem.
• Let \(S_{\min}\) be the minimum element among the strings in \(S\) with respect to the ordering \(\preceq\). This can be found in \(O(N\max|S_i|)\) time by actually comparing the strings by \(\preceq\).

If \(K=\infty\)

We have \(T_{\infty}=S_{\min}\times \infty\). (Proof)

1. Suppose \(T_{\infty}\) starts with the string \(S_i\). Then \(T_{\infty}=S_i+T_{\infty}\), so \(T_{\infty}=S_i\times \infty\).
2. Take \(i\) arbitrarily. Let \(A=S_{\min}\times|S_i|\) and \(B=S_i\times|S_{\min}|\). Then \(S_{\min} \preceq S_i\), which implies \(A+B\leq B+A\); since \(|A|=|B|\), we have \(A\leq B\). Thus, \(S_{\min}\times\infty=A\times\infty\leq B\times\infty = S_i\times\infty\).

If \(K <\infty\)

\(T_K\) is a prefix of \(T_{\infty}\).
(Proof)

1. If \(T_K>T_\infty\), then \(T_K>T_\infty>S_{\min}\times K\), which is a contradiction.

2. If \(T_K<T_\infty\) but \(T_K\) is not a prefix of \(T_\infty\), then \(T_K\times\infty<T_{\infty}\), which is a contradiction.

Original problem

Therefore, the problem can be reduced to finding the shortest prefix of \(T_\infty\) that can be obtained by concatenating \(K\) elements of \(S\). With a DP (Dynamic Programming) where \(\mathrm{dp}[n][p]\) is the minimum length of a prefix of \(T_\infty[p:]\) that can be obtained by concatenating \(n\) elements of \(S\), the problem can be solved in a total of \(O(|S_{\min}|^2K)\) with proper precalculation.