/* -*- coding: utf-8 -*- * * 1192.cc: No.1192 捊郹戆戗 - yukicoder */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /* constant */ const int MAX_N = 100000; const int INF = 1 << 30; /* typedef */ /* global variables */ char s[MAX_N + 4], t[MAX_N + 4], w[MAX_N + 4]; int scs[MAX_N + 1][26], tcs[MAX_N + 1][26]; int sbss[MAX_N + 1]; /* subroutines */ void calccs(int n, char s[], int cs[][26]) { fill(cs[n], cs[n] + 26, INF); for (int i = n - 1; i >= 0; i--) { copy(cs[i + 1], cs[i + 1] + 26, cs[i]); cs[i][s[i] - 'a'] = i; } } /* main */ int main() { scanf("%s%s", s, t); int n = strlen(s), m = strlen(t); calccs(n, s, scs); calccs(m, t, tcs); sbss[n] = m; for (int i = n - 1, j = m - 1; i >= 0; i--) { while (j >= 0 && t[j] != s[i]) j--; sbss[i] = j; if (j >= 0) j--; } //for (int i = 0; i <= n; i++) printf("%d ", sbss[i]); putchar('\n'); if (sbss[0] >= 0) puts("-1"); else { int i = 0, j = 0, k = 0; for (; j < m;) { for (int c = 0; c < 26; c++) { int i1 = scs[i][c] + 1, j1 = tcs[j][c] + 1; if (i1 <= n && sbss[i1] < j1) { //printf("w[%d]=%c, i=%d->%d, j=%d->%d\n", k, 'a' + c, i, i1, j, j1); w[k++] = 'a' + c; i = i1, j = j1; break; } } } for (int c = 0; c < 26; c++) if (scs[i][c] < n) { w[k++] = 'a' + c; break; } puts(w); } return 0; }