use proconio::{input, marker::Chars};
use nekolib::{ds::N1Rmq, seq::SuffixArray};
fn main() {
input! {
s: Chars,
t: Chars,
}
let lcp = LcpQuery::new(&s, &t);
let n = s.len();
let m = t.len();
let max = m + n;
let mut v = vec![0; 2 * max + 1];
let off = max;
v[off + 1] = 0;
let mut from_plus = vec![vec![false; 2 * max + 1]; max + 1];
let mut last = (0, 0);
'outer: for d in 0..=max {
for k in (off - d..=off + d).step_by(2) {
let mut x = if k == off - d || (k != off + d && v[k - 1] < v[k + 1])
{
from_plus[d][k] = true;
v[k + 1]
} else {
from_plus[d][k] = false;
v[k - 1] + 1
};
let mut y = x + off - k;
if x < n && y < m {
let diag = lcp.query(x, y);
x += diag;
y += diag;
}
v[k] = x;
if x >= n && y >= m {
eprintln!("len: {}", d);
last = (d, k);
break 'outer;
}
}
}
let mut res = vec![];
let (mut d, mut k) = last;
let (mut x, mut y) = (n, m);
while x > 0 || y > 0 {
while x > 0 && y > 0 && s[x - 1] == t[y - 1] {
x -= 1;
y -= 1;
res.push(s[x]);
// res.push(Zero(s[x]));
}
if (x, y) == (0, 0) {
break;
}
if from_plus[d][k] {
k += 1;
y -= 1;
// res.push(Pos(t[y]));
} else {
k -= 1;
x -= 1;
// res.push(Neg(s[x]));
}
d -= 1;
}
let res: String = res.into_iter().rev().collect();
println!("{}", res);
}
// #[derive(Clone, Copy, Debug, Eq, PartialEq)]
// enum Diff {
// Pos(char),
// Zero(char),
// Neg(char),
// }
// use Diff::{Neg, Pos, Zero};
struct LcpQuery {
isa: Vec<usize>,
lcpa: N1Rmq<usize>,
first_len: usize,
}
impl LcpQuery {
pub fn new(s: &[char], t: &[char]) -> Self {
let max = *s.iter().chain(t).max().unwrap_or(&'\0') as u32;
let s_t: Vec<_> = s
.iter()
.map(|&c| c as u32)
.chain(std::iter::once(max + 1))
.chain(t.iter().map(|&c| c as u32))
.collect();
let sa: SuffixArray<_> = s_t.into();
let lcpa = sa.lcpa();
let isa = {
let mut isa = vec![0; s.len() + t.len() + 2];
for i in 0..isa.len() {
isa[sa[i]] = i;
}
isa
};
Self { isa, lcpa: lcpa.into(), first_len: s.len() }
}
pub fn query(&self, i: usize, j: usize) -> usize {
let si = self.isa[i] + 1;
let sj = self.isa[self.first_len + 1 + j] + 1;
let (l, r) = (si.min(sj), si.max(sj));
*self.lcpa.min(l, r)
}
}
/// This module is bundled automatically.
/// See <https://rsk0315.github.io/library-rs/nekolib/> for documentation.
pub mod nekolib {
pub mod ds {
pub mod n1_rmq {
pub struct N1Rmq<T> {
base: Vec<T>,
large: SparseTable<T>,
small: Vec<usize>,
types: Vec<usize>,
b: usize,
}
impl<T: Clone + Ord> From<Vec<T>> for N1Rmq<T> {
fn from(base: Vec<T>) -> Self {
let n = base.len();
let lg_n = n.next_power_of_two().trailing_zeros();
let b = 1.max(lg_n / 4) as usize;
let mut large = vec![];
let mut small = vec![0; (1 << (2 * b)) * b * b];
let mut types = vec![];
let mut seen = vec![false; 1 << (2 * b)];
for ch in base.chunks(b) {
large.push(ch.iter().min().unwrap().clone());
let ty = cartesian_tree(ch);
types.push(ty);
if !seen[ty] {
for l in 0..ch.len() {
let mut j = l;
for r in l..ch.len() {
if ch[j] > ch[r] {
j = r;
}
let i = (ty * b + l) * b + r;
small[i] = j;
}
}
seen[ty] = true;
}
}
let large: SparseTable<_> = large.into();
Self { base, large, small, types, b }
}
}
impl<T: Clone + Ord> N1Rmq<T> {
fn index(
&self,
bucket: usize,
start: usize,
end: usize,
) -> usize {
let b = self.b;
(self.types[bucket] * b + start) * b + end
}
pub fn min(&self, l: usize, r: usize) -> &T {
let b = self.b;
let lb = l / b;
let rb = (r - 1) / b;
if lb == rb {
return &self.base[lb * b
+ self.small[self.index(lb, l % b, (r - 1) % b)]];
}
let mut res = if l % b == 0 {
self.large.min(lb, lb + 1)
} else {
&self.base
[lb * b + self.small[self.index(lb, l % b, b - 1)]]
};
res = res.min(if r % b == 0 {
self.large.min(rb, rb + 1)
} else {
&self.base[rb * b
+ self.small[self.index(rb, 0, (r - 1) % b)]]
});
if lb + 1 < rb {
res = res.min(self.large.min(lb + 1, rb));
}
res
}
}
fn cartesian_tree<T: Ord>(a: &[T]) -> usize {
let mut stack = vec![];
let mut res = 1;
for ai in a {
while let Some(&last) = stack.last() {
if last > ai {
stack.pop();
res <<= 1;
} else {
break;
}
}
stack.push(ai);
res = res << 1 | 1;
}
res << (stack.len() - 1)
}
struct SparseTable<T> {
base: Vec<T>,
table: Vec<Vec<usize>>,
}
impl<T: Ord> From<Vec<T>> for SparseTable<T> {
fn from(base: Vec<T>) -> Self {
let mut table = vec![];
let n = base.len();
table.push((0..n).collect::<Vec<_>>());
for sh in 1.. {
let last = table.last().unwrap();
let len = 1 << sh;
if len >= n {
break;
}
let mut cur = vec![0; n - len + 1];
for i in len..=n {
let (il, ir) = (
last[i - len],
last[i - len + (1 << (sh - 1))],
);
cur[i - len] =
if base[il] < base[ir] { il } else { ir };
}
table.push(cur);
}
Self { base, table }
}
}
impl<T: Ord> SparseTable<T> {
pub fn min(&self, i: usize, j: usize) -> &T {
let len = j - i;
if len <= 1 {
return &self.base[i];
}
let sh =
len.next_power_of_two().trailing_zeros() as usize - 1;
let [il, ir] =
[self.table[sh][i], self.table[sh][j - (1 << sh)]];
(&self.base[il]).min(&self.base[ir])
}
}
}
pub use n1_rmq::N1Rmq;
}
pub mod seq {
pub mod suffix_array {
use std::cmp::Ordering::{Equal, Greater, Less};
use std::collections::{BTreeMap, BTreeSet};
use std::fmt::Debug;
use std::ops::Index;
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct SuffixArray<T: Ord> {
buf: Vec<T>,
sa: Vec<usize>,
}
impl<T: Ord> From<Vec<T>> for SuffixArray<T> {
fn from(buf: Vec<T>) -> Self {
let buf_usize = hash(&buf);
let sa = sa_is(&buf_usize);
Self { buf, sa }
}
}
impl From<String> for SuffixArray<char> {
fn from(buf: String) -> Self {
let buf: Vec<_> = buf.as_str().chars().collect();
let buf_usize = hash_chars(&buf);
let sa = sa_is(&buf_usize);
Self { buf, sa }
}
}
fn hash<T: Ord>(buf: &[T]) -> Vec<usize> {
let enc: BTreeSet<_> = buf.iter().collect();
let enc: BTreeMap<_, _> =
enc.into_iter().enumerate().map(|(i, x)| (x, i)).collect();
buf.iter()
.map(|x| enc[x] + 1)
.chain(std::iter::once(0))
.collect()
}
fn hash_chars(buf: &[char]) -> Vec<usize> {
let max = match buf.iter().max() {
Some(&c) => c as usize,
None => return vec![0],
};
let enc = {
let mut enc = vec![0; max + 1];
for &c in buf {
enc[c as usize] = 1;
}
for i in 1..=max {
enc[i] += enc[i - 1];
}
enc
};
buf.iter()
.map(|&x| enc[x as usize])
.chain(std::iter::once(0))
.collect()
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
enum LsType {
LType,
SType(bool),
}
use LsType::{LType, SType};
fn count_freq(buf: &[usize]) -> Vec<usize> {
let mut res = vec![0; buf.len()];
buf.iter().for_each(|&x| res[x] += 1);
res
}
fn inv_perm(buf: &[usize]) -> Vec<usize> {
let mut res = vec![0; buf.len()];
buf.iter().enumerate().for_each(|(i, &x)| res[x] = i);
res
}
fn ls_classify(buf: &[usize]) -> Vec<LsType> {
let mut res = vec![SType(false); buf.len()];
for i in (0..buf.len() - 1).rev() {
res[i] = match buf[i].cmp(&buf[i + 1]) {
Less => SType(false),
Equal => res[i + 1],
Greater => LType,
};
}
for i in 1..buf.len() {
if let (LType, SType(_)) = (res[i - 1], res[i]) {
res[i] = SType(true);
}
}
res
}
fn bucket_head(count: &[usize]) -> Vec<usize> {
let n = count.len();
let mut head: Vec<_> = std::iter::once(&0)
.chain(&count[..n - 1])
.cloned()
.collect();
for i in 1..n {
head[i] += head[i - 1];
}
head
}
fn bucket_tail(count: &[usize]) -> Vec<usize> {
let mut tail = count.to_vec();
for i in 1..count.len() {
tail[i] += tail[i - 1];
}
tail
}
fn induce(
buf: &[usize],
sa: &mut [Option<usize>],
count: &[usize],
ls: &[LsType],
) {
let mut head = bucket_head(count);
for i in 0..sa.len() {
if let Some(j) = sa[i] {
if j > 0 && ls[j - 1] == LType {
sa[head[buf[j - 1]]] = Some(j - 1);
head[buf[j - 1]] += 1;
}
}
}
let mut tail = bucket_tail(count);
for i in (1..count.len()).rev() {
if let Some(j) = sa[i] {
if j > 0 && ls[j - 1] != LType {
tail[buf[j - 1]] -= 1;
sa[tail[buf[j - 1]]] = Some(j - 1);
}
}
}
}
fn reduce(
buf: &[usize],
lms: &[usize],
ls: &[LsType],
) -> Vec<usize> {
if lms.len() <= 1 {
return vec![0; lms.len()];
}
let e = |(i0, i1)| {
if (ls[i0], ls[i1]) == (SType(true), SType(true)) {
Some(true)
} else if ls[i0] != ls[i1] || buf[i0] != buf[i1] {
Some(false)
} else {
None
}
};
let mut map = vec![0; buf.len()];
map[lms[1]] = 1;
let mut x = 1;
for i in 2..lms.len() {
let equiv = buf[lms[i]] == buf[lms[i - 1]]
&& (lms[i] + 1..)
.zip(lms[i - 1] + 1..)
.find_map(e)
.unwrap();
if !equiv {
x += 1;
}
map[lms[i]] = x;
}
(0..buf.len())
.filter_map(|i| match ls[i] {
SType(true) => Some(map[i]),
_ => None,
})
.collect()
}
fn sa_is(buf: &[usize]) -> Vec<usize> {
let len = buf.len();
let count = count_freq(buf);
if count.iter().all(|&x| x == 1) {
return inv_perm(buf);
}
let ls = ls_classify(buf);
let mut sa = vec![None; len];
let mut tail = bucket_tail(&count);
for i in (1..len).rev().filter(|&i| ls[i] == SType(true)) {
tail[buf[i]] -= 1;
sa[tail[buf[i]]] = Some(i);
}
induce(buf, &mut sa, &count, &ls);
let lms: Vec<_> = sa
.into_iter()
.map(std::option::Option::unwrap)
.filter(|&i| ls[i] == SType(true))
.collect();
let rs_sa = sa_is(&reduce(buf, &lms, &ls));
let lms: Vec<_> =
(0..len).filter(|&i| ls[i] == SType(true)).collect();
let mut tail = bucket_tail(&count);
let mut sa = vec![None; len];
for i in rs_sa.into_iter().rev() {
let j = lms[i];
tail[buf[j]] -= 1;
sa[tail[buf[j]]] = Some(j);
}
induce(buf, &mut sa, &count, &ls);
sa.into_iter().map(std::option::Option::unwrap).collect()
}
impl<T: Ord> SuffixArray<T> {
pub fn search(
&self,
pat: &[T],
) -> impl Iterator<Item = usize> + '_ {
let lo = {
let mut lt = 1_usize.wrapping_neg();
let mut ge = self.sa.len();
while ge.wrapping_sub(lt) > 1 {
let mid = lt.wrapping_add(ge.wrapping_sub(lt) / 2);
let pos = self.sa[mid];
match self.buf[pos..].cmp(pat) {
Less => lt = mid,
_ => ge = mid,
}
}
ge
};
if lo >= self.sa.len() {
return self.sa[lo..lo].iter().cloned();
}
let hi = {
let mut le = lo.wrapping_sub(1);
let mut gt = self.sa.len();
while gt.wrapping_sub(le) > 1 {
let mid = le.wrapping_add(gt.wrapping_sub(le) / 2);
let pos = self.sa[mid];
let len = pat.len().min(self.buf[pos..].len());
match self.buf[pos..pos + len].cmp(pat) {
Greater => gt = mid,
_ => le = mid,
}
}
gt
};
self.sa[lo..hi].iter().cloned()
}
pub fn lcpa(&self) -> Vec<usize> {
let n = self.buf.len();
let mut rank = vec![0; n + 1];
for i in 0..=n {
rank[self.sa[i]] = i;
}
let mut h = 0;
let mut res = vec![0; n + 1];
for i in 0..n {
let j = self.sa[rank[i] - 1];
if h > 0 {
h -= 1;
}
while j + h < n && i + h < n {
if self.buf[j + h] != self.buf[i + h] {
break;
}
h += 1;
}
res[rank[i]] = h;
}
res
}
pub fn into_inner(self) -> Vec<usize> { self.sa }
}
impl SuffixArray<char> {
pub fn search_str(
&self,
pat: &str,
) -> impl Iterator<Item = usize> + '_ {
let pat: Vec<_> = pat.chars().collect();
self.search(&pat)
}
}
impl<T: Ord> Index<usize> for SuffixArray<T> {
type Output = usize;
fn index(&self, i: usize) -> &usize { &self.sa[i] }
}
impl<T: Ord> From<SuffixArray<T>> for Vec<usize> {
fn from(sa: SuffixArray<T>) -> Self { sa.sa }
}
}
pub use suffix_array::SuffixArray;
}
}