Codejam Round 1A 2020 Pattern Matching（构造）

本文主要是介绍Codejam Round 1A 2020 Pattern Matching（构造），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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 BL, 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 104 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

Output

2
5
*CONUTS
*COCONUTS
*OCONUTS
*CONUTS
*S
2
*XZ
*XYZ

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
HO
HELLO
HELLO
HE
HELLO and HELLOGOODBYEHELLO are examples of acceptable answers. OTHELLO and HELLOO would not be acceptable.

2
CODE
JAM
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
ACE
BD*
ABCDE and ABUNDANCE are among the possible acceptable answers, but BOLDFACE is not.

2
ACE
BD
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.

round1A感觉好难啊。A,B是构造，C是模拟。想了好久的A，写到第二个点的时候，发现只需要匹配前后缀。然后到了第三个点，发现中间部分只要把所有字符串加上来就好了。本来B题的前两个点也看出了了，只需要输出边上的，但是最后BUG没改完。码力还是不行。。。
题意：
$*$ 可以代表任意字符串，包括空串。
给一系列带 $*$ 的字符串，求构造一个字符串（不带 $*$ ，使得其能匹配所有字符串）

思路：
需要考虑的只有前后缀。
构造出来的新串只要加上最长的前缀和最长的后缀，中间部分是所有字符串非前后缀加上来。

如果前缀最长的字符串的前缀，不能通过其后缀匹配其他字符串前缀，那肯定弄不了,后缀同理。

ACNEW
逻辑清晰了点

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <set>
#include <queue>
#include <cmath>
#include <vector>
#include <map>
#include <ctime>
#include <stack>using namespace std;typedef long long ll;
const int maxn = 100 + 7;
int n;
string s[maxn];string get_pre(string &str) {string ans;for(int i = 0;i < str.length();i++) {if(str[i] == '*') break;ans += str[i];}return ans;
}string get_suf(string &str) {string ans;for(int i = str.length() - 1;i >= 0;i--) {if(str[i] == '*') break;ans += str[i];}reverse(ans.begin(),ans.end());return ans;
}bool equal_pre(string &str1,string &str2) {for(int i = 0;i < str2.length();i++) {if(str2[i] == '*') break;if(str1[i] != str2[i]) return false;}return true;
}bool equal_suf(string &str1,string &str2) {int cnt1 = str1.length() - 1,cnt2 = str2.length() - 1;for(int i = str1.length() - 1;i >= 0;i--) {if(cnt1 < 0 || cnt2 < 0) break;if(str2[cnt2] == '*') break;if(str1[cnt1] != str2[cnt2]) return false;cnt1--;cnt2--;}return true;
}bool check(string &pre,string &suf) {for(int i = 1;i <= n;i++) {string pre_now = get_pre(s[i]);if(!equal_pre(pre,pre_now)) return false;string suf_now = get_suf(s[i]);if(!equal_suf(suf,suf_now)) return false;}return true;
}void Print(string &pre,string &suf) {cout << pre;for(int i = 1;i <= n;i++) {for(int j = 0;j < s[i].length();j++) {if(s[i][j] == '*') continue;cout << s[i][j];}}cout << suf << endl;
}int main() {int T;scanf("%d",&T);int kase = 0;while(T--) {scanf("%d",&n);int mx_pre = 0,mx_suf = 0;string pre,suf;for(int i = 1;i <= n;i++) {cin >> s[i];string pre_now = get_pre(s[i]);int len1 = pre_now.length();if(len1 > mx_pre) {mx_pre = len1;pre = pre_now;}string suf_now = get_suf(s[i]);int len2 = suf_now.length();if(len2 > mx_suf) {mx_suf = len2;suf = suf_now;}}printf("Case #%d: ",++kase);if(check(pre,suf)) {Print(pre,suf);} else {cout << "*" << endl;}}return 0;
}

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <iostream>
#include <string>
#include <vector>using namespace std;string s[1005];
int n;
int mx_s = 0,mx_e = 0;
string sta,ed;bool check1(string a,string b) {//前缀int len1 = a.length(),len2 = b.length();for(int i = 0;i < len1;i++) {if(b[i] == '*') break;if(a[i] != b[i]) return false;}return true;
}bool check2(string a,string b) {//后缀int len1 = a.length(),len2 = b.length();for(int i = len1 - 1,j = len2 - 1;i >= 0 && j >= 0;i--,j--) {if(b[j] == '*') break;if(a[i] != b[j]) return false;}return true;
}void Cin() {for(int i = 1;i <= n;i++) {cin >> s[i];int len = s[i].length();for(int j = 0;j < len;j++) {if(s[i][j] == '*') {if(mx_s < j && j != 0) {mx_s = j;sta = s[i].substr(0,j);}break;}}for(int j = len - 1;j >= 0;j--) {if(s[i][j] == '*') {if(mx_e < len - j && j != len - 1) {ed = s[i].substr(j + 1,len - 1 - j);mx_e = len - 1 - j;}break;}}}
}
bool judge() {for(int i = 1;i <= n;i++) {if(!check1(sta,s[i]) || !check2(ed,s[i])) {return false;}}return true;
}int main() {int T;scanf("%d",&T);int kase = 0;while(T--) {scanf("%d",&n);mx_s = 0,mx_e = 0;sta.clear();ed.clear();Cin();int flag = judge();printf("Case #%d: ",++kase);if(flag) {cout << sta;for(int i = 1;i <= n;i++) {for(int j = 0;j < s[i].size();j++) {if(s[i][j] == '*') continue;cout << s[i][j];}}cout << ed;printf("\n");}else {printf("*\n");}}return 0;
}