Problem
Many terminals use asterisks (*) to signify “any string”, including the empty string. For example, when listing files matching BASH*, a terminal may list BASH, BASHER and BASHFUL. For *FUL, it may list BEAUTIFUL, AWFUL and BASHFUL. When listing B*L, BASHFUL, BEAUTIFUL and BULL may be listed.
In this problem, formally, a pattern is a string consisting of only uppercase English letters and asterisks (*), and a name is a string consisting of only uppercase English letters. A pattern p matches a name m if there is a way of replacing every asterisk in p with a (possibly empty) string to obtain m. Notice that each asterisk may be replaced by a different string.
Given N patterns, can you find a single name of at most $10^4$ letters that matches all those patterns at once, or report that it cannot be done?
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line with a single integer N: the number of patterns to simultaneously match. Then, N lines follow, each one containing a single string Pi representing the i-th pattern.
Output
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is any name containing at most 104 letters such that each Pi matches y according to the definition above, or * (i.e., just an asterisk) if there is no such name.
Limits
Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
2 ≤ N ≤ 50.
2 ≤ length of Pi ≤ 100, for all i.
Each character of Pi is either an uppercase English letter or an asterisk (*), for all i.
At least one character of Pi is an uppercase English letter, for all i.
Test set 1 (Visible Verdict)
Exactly one character of Pi is an asterisk (*), for all i.
The leftmost character of Pi is the only asterisk (*), for all i.
Test set 2 (Visible Verdict)
Exactly one character of Pi is an asterisk (*), for all i.
Test set 3 (Visible Verdict)
At least one character of Pi is an asterisk (*), for all i.
Sample
Input
2
5
*CONUTS
*COCONUTS
*OCONUTS
*CONUTS
*S
2
*XZ
*XYZ
Output
Case #1: COCONUTS
Case #2: *
In Sample Case #1, there are other possible answers, including COCOCONUTS and ILIKECOCONUTS. Neither COCONUTSAREGREAT nor COCOANUTS would be acceptable. Notice that the same pattern may appear more than once within a test case.
In Sample Case #2, there is no acceptable name, so the answer is *.
The following cases could not appear in Test Set 1, but could appear in Test Set 2 or Test Set 3:
4
H*O
HELLO*
*HELLO
HE*
HELLO and HELLOGOODBYEHELLO are examples of acceptable answers. OTHELLO and HELLOO would not be acceptable.
2
CO*DE
J*AM
There is no name that matches both patterns, so the answer would be *.
2
CODE*
*JAM
CODEJAM is one example of an acceptable answer.
The following cases could not appear in Test Set 1 or Test Set 2, but could appear in Test Set 3:
2
A*C*E
*B*D*
ABCDE and ABUNDANCE are among the possible acceptable answers, but BOLDFACE is not.
2
A*C*E
*B*D
There is no name that matches both patterns, so the answer would be *.
2
**Q**
*A*
QUAIL and AQ are among the possible acceptable answers here.
Analysis
Test Set 1
In Test Set 1, each pattern forces our answer to have a certain suffix, and we first need to check whether the patterns introduce conflicting requirements for that suffix.
Consider the letter strings coming after the initial asterisk in each pattern. We can find the longest of those strings (or any longest, if there is a tie); call that string L. Then at least one answer exists if (and only if) every other string is a suffix of L; note that we are considering L itself to be a suffix of L. We can check each other string against L by starting at the ends of both strings and stepping backwards through them in tandem until we find a discrepancy or run out of letters to check. If we ever find a discrepancy, then the case has no answer, but otherwise, we know that L itself is an acceptable answer.
Test Set 2
In Test Set 2, we can divide the patterns into (1) patterns that start with an asterisk, (2) patterns that end with an asterisk, and (3) patterns with an asterisk in the middle.
A type (1) pattern requires the output word to have a certain suffix, just as in Test Set 1. A type (2) pattern requires the output word to have a certain prefix. A type (3) pattern introduces both of these requirements, and we can split it into a suffix requirement and a prefix requirement, and then handle those separately.
Then, we can apply our strategy from Test Set 1 twice: once for the prefix constraints (with the algorithm modified to compare prefixes instead), and once for the suffix constraints. We can concatenate the two results together to obtain a valid answer that is certainly short enough (since it can be at most 99+99 characters long).
Test Set 3
We can generalize the idea above into a solution for Test Set 3. Each pattern p in Test Set 3 also prescribes a prefix of the output word (the prefix of p up to the first asterisk) and a suffix of the output word (the suffix of p starting after the last asterisk). If we allow empty prefixes and suffixes, we get exactly one of each for every pattern. We can handle those in the same way we did for Test Set 2, ending up with a prefix P and a suffix S for the output as long as we do not find a discrepancy in either phase.
However, for patterns that have more than one asterisk, we can also have a middle part, which imposes a new type of requirement. Suppose we parse the parts between the asterisks of a pattern so that X is the prefix up to the first asterisk, Y is the suffix after the last asterisk, and M1, M2, …, Mk are the strings in between the asterisks, in order. After checking that X is a prefix of P and Y is a suffix of S, as before, all that remains to ensure is that the pattern M1*M2*…*Mk is present somewhere within the output word, strictly between P and S.
Let us call M1M2…Mk — that is, the word that occurs in between the first and last asterisks with any other asterisk removed — the middle word. If we make sure a pattern’s middle word occurs in the output word outside of P and S, then we fulfill the extra requirement. We can then build a full valid output then by starting with P, then adding the middle word of every pattern in any order, then appending S. We make sure to correctly handle words with a single asterisk or only consecutive asterisks by making their middle words the empty string. Since each middle word contains at most 98 characters, and the prefix and suffix contain at most 99 characters each, the output built this way has at most 99 × 2 + 50 × 98 characters, which is within the limit of $10^4$ .
/*
主要思路：
以*为分割，把每个string分为前缀，若干个中缀，后缀。
答案的前缀取最长前缀，（因为多出来的部分可以塞到其他的*里）
同理答案的后缀取最长后缀，
中缀随意塞在中间即可。
若前后缀无法互相包含则无解。
*/
/**
* author: tourist
* created: 11.04.2020 03:52:40
**/
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int tt;
cin >> tt;
for (int qq = 1; qq <= tt; qq++) {
cout << "Case #" << qq << ": ";
int n;
cin >> n;
vector<string> strs(n);//用string的vector存下输入
for (int i = 0; i < n; i++) {
cin >> strs[i];
}
string pref = "";//初始化前缀为空
string suf = "";//初始化后缀为空
vector<string> sub;
bool ok = true;
for (string& s : strs) {
//下面先处理前缀，并把后缀扫好
int last = -1;//上次遇到字母的位置，初始时last为-1
for (int i = 0; i < (int) s.size(); i++) {//每个string每位遍历
if (s[i] == '*') {//若该位为*时
if (last == -1) {//遇到该string的第一个*时
string other_pref = s.substr(0, i);//提取0到该位之前的前缀
if (other_pref.size() > pref.size()) {//若该前缀比原先的前缀长就替换
swap(pref, other_pref);
}
if (pref.substr(0, other_pref.size()) != other_pref) {
//若现有前缀与当前最长前缀不符，则没有符合题意的答案
ok = false;
break;
}
} else {
sub.push_back(s.substr(last + 1, i - last - 1));
//存入从上次遇到*之后，到这次*之前的这段子串
}
last = i;//上次遇到字母的位置更新为i
}
}
if (!ok) {
break;//有冲突时直接break输出不存在
}
//开始处理后缀
string other_suf = s.substr(last + 1);
//后缀为上一次遇到字母之后到结尾为止的字串
//提取最长的后缀
if (other_suf.size() > suf.size()) {
swap(suf, other_suf);
}
//若后缀无法相等，也不存在合适的答案
if (suf.substr(suf.size() - other_suf.size()) != other_suf) {
ok = false;
break;
}
}
if (!ok) {
cout << "*" << '\n';
} else {
//输出前缀+塞在里面的中缀+后缀为答案
cout << pref;
for (auto& s : sub) {
cout << s;
}
cout << suf << '\n';
}
}
return 0;
}
