Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <string>
- using namespace std;
- struct let {
- int a[26];
- };
- int dp[2050][2050], p[2050][2050], ans[2050][2050], len;
- bool amb[2050][2050];
- string dict1[10050], t, segm[2050][2050], str;
- vector < pair<string, int> > dict2[150];
- void solve(int l, int r) {
- dp[l][r] = 0;
- int cnt = 0;
- if (r - l + 1 <= 100) {
- int lb = -1, rb = (int)dict2[r - l + 1].size() - 1;
- while (lb + 1 < rb) {
- int mb = (lb + rb) / 2;
- if (dict2[r - l + 1][mb].first < segm[l][r])
- lb = mb;
- else
- rb = mb;
- }
- if (rb >= 0) {
- if (dict2[r - l + 1][rb].first == segm[l][r]) {
- dp[l][r] = 1;
- cnt++;
- p[l][r] = r;
- ans[l][r] = dict2[r - l + 1][rb].second;
- }
- if (rb < (int)dict2[r - l + 1].size() - 1 && dict2[r - l + 1][rb + 1].first == segm[l][r])
- cnt++;
- }
- }
- for (int i = l; i < r; i++) {
- if (dp[l][i] == -1)
- solve(l, i);
- if (dp[i + 1][r] == -1)
- solve(i + 1, r);
- if (dp[l][i] == 1 && dp[i + 1][r] > 0) {
- if (amb[i + 1][r])
- cnt++;
- dp[l][r] = dp[l][i] + dp[i + 1][r];
- cnt++;
- p[l][r] = i;
- }
- }
- if (cnt > 1)
- amb[l][r] = true;
- }
- void rec(int l, int r) {
- if (p[l][r] == r) {
- cout << dict1[ans[l][r]];
- if (r != len - 1)
- cout << " ";
- }
- else {
- rec(l, p[l][r]);
- rec(p[l][r] + 1, r);
- }
- }
- bool cmp(pair<string, int> a, pair<string, int> b) {
- return a.first < b.first;
- }
- int main()
- {
- for (int i = 0; i < 2000; i++)
- for (int j = 0; j < 2000; j++)
- dp[i][j] = -1;
- int n;
- cin >> str;
- len = str.length();
- for (int i = 0; i < min(100, len); i++)
- for (int j = 0; j < len - i; j++) {
- segm[j][j + i] = str.substr(j, i + 1);
- sort(segm[j][j + i].begin(), segm[j][j + i].end());
- }
- cin >> n;
- for (int i = 0; i < n; i++) {
- cin >> dict1[i];
- t = dict1[i];
- sort(t.begin(), t.end());
- dict2[t.length()].push_back(make_pair(t, i));
- }
- for (int i = 1; i <= 100; i++)
- sort(dict2[i].begin(), dict2[i].end(), cmp);
- solve(0, len - 1);
- if (dp[0][len - 1] == 0)
- cout << "impossible";
- else if (amb[0][len - 1])
- cout << "ambiguous";
- else
- rec(0, len - 1);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement