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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
| #include <vector>
using namespace std;
struct Diophantine {
int x, y, d;
};
Diophantine extendedEuclid(int a, int b) {
if(b == 0) {
return {1, 0, a};
} else {
auto dio = extendedEuclid(b, a % b);
int x1 = dio.y;
int y1 = dio.x - (a / b) * dio.y;
return {x1, y1, dio.d};
}
}
Diophantine diophantineEquation(int a, int b, int v) {
if(v % gcd(a,b) != 0)
return {-1, -1, -1};
return extendedEuclid(a, b);
}
bool equal(string& str, int& pos, string& pattern) {
int i = 0, n = pattern.length(), m = str.length();
while(i < n and pos < m) {
if(pattern[i] != str[pos]) return false;
i++; pos++;
}
return i == n;
}
bool helper(int xlen, int ylen, int xpos, int ypos, string& str, string& pattern) {
if(xlen <= 0 or ylen <= 0) return false;
string X = str.substr(ylen * xpos, xlen);
string Y = str.substr(xlen * ypos, ylen);
int p = 0;
for(auto& ch : pattern) {
if(!equal(str, p, ch == 'x' ? X : Y))
return false;
}
return true;
}
vector<string> patternMatcher(string pattern, string str) {
int a = 0, b = 0, xpos = INT_MAX, ypos = INT_MAX;
for(int i = 0; i < pattern.length(); i++) {
if(pattern[i] == 'x') {
a++;
xpos = min(xpos, i);
} else {
b++;
ypos = min(ypos, i);
}
}
if(!a or !b) {
if(a == b) return {};
string match = str.substr(0, str.length() / max(a,b));
int p = 0;
for(auto& ch : pattern) {
if(!equal(str, p, match))
return {};
}
return {a ? match : "" , a ? "" : match};
}
auto dio = diophantineEquation(a, b, str.length());
if(dio.d == -1) return {};
int X = dio.x * str.length() / gcd(a,b);
int Y = dio.y * str.length() / gcd(a, b);
int s = round(1.0 * -X / (b / dio.d));
int e = round(1.0 * Y / (a / dio.d));
for(int i = s; i <= e; i++) {
int d = dio.d;
int x = X + (b / d) * i;
int y = Y - (a / d) * i;
if(helper(x, y, xpos, ypos, str, pattern)) {
string X = str.substr(y * xpos, x);
string Y = str.substr(x * ypos, y);
return {X, Y};
}
}
return {};
}
|
