pattern.cpp


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

#include <bits/stdc++.h>
using namespace std;

int main() {
	if (fopen("in", "r")) freopen("in", "r", stdin), freopen("out", "w", stdout);

	int T;
	cin >> T;
	for (int t = 1; t <= T; ++t) {
		cout << "Case #" << t << ": ";
		
		int N;
		cin >> N;
		string P[55]; // patterns
		for (int i = 0; i < N; ++i) cin >> P[i];
		
		string l, m, r; // left, middle, end parts of final answer
		bool ans = 1; // flag so we can quickly break when no solution exists
		for (int i = 0; i < N && ans; ++i) {
			// tokenize string
			vector<string> parts;
			parts.push_back("");
			for (auto& c : P[i]) {
				if (c == '*') parts.push_back(""); // add new string
				else parts.back() += c; // add c to current string
			}
			
			string& s = parts.front(); // leftmost part
			for (int j = 0; j < s.size() && ans; ++j) {
				if (j >= l.size()) l.push_back(s[j]); // extend l
				else if (s[j] != l[j]) ans = 0; // s doesn't match with current l
			}
			
			s = parts.back(); // rightmost part
			reverse(s.begin(), s.end());
			for (int j = 0; j < s.size() && ans; ++j) {
				if (j >= r.size()) r.push_back(s[j]); // extend r
				else if (s[j] != r[j]) ans = 0; // s doesn't match with current r
			}
			
			// add other parts to the middle string
			for (int j = 1; j < parts.size() - 1 && ans; ++j) m += parts[j];
		}

		// Creates at most ≈5000 < 10000 characters
		reverse(r.begin(), r.end());
		cout << (ans ? l + m + r : "*") << '\n';
	}
}