Блог пользователя Aayushi_Bhardwaj_Pataka

Number of Shortest Supersequences
Автор Aayushi_Bhardwaj_Pataka, история, 7 лет назад, По-английски

Given two strings s and t. Find the number of ways to make a new string c such that both s and t appear as subsequences in c and also c has minimum length among all such strings possible.

I was able to figure out that the shortest length will be len(s) + len(t) — len(lcs(s, t)) but unable to approach further via any recursive/combinatorial approach.

  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Limit on the lengths?

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Anyone able to solve this?

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Find the LCS (subsequence) of s and t and create the initial c = lcs(s, t). Now if we remove the LCS from s and t we will have length(lcs(s, t)) + 1 groups of characters which should be inserted before a certain letter in the inital c. Well then a simple construction would be to just add both 1-st groups before first letter of the the LCS (c), both 2-nd groups before the second letter and so on.

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    It doesn't work for s = "ab", t = "ba".
    If c = lcs(s, t) = "a", the only answer you will find is "bab", though there are two answers.

    → Ответить
»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

d[i][j] = shortest length of string, such that it contains first i symbols of first string as subsequence, and first j symbols of the second string as a subsequence.

dp[i][j] = number of ways to build string with length d[i][j], such that it contains first i symbols of first string as subsequence, and first j symbols of the second string as a subsequence.

transitions:

s[i+1] == t[j+1] => d[i+1][j+1] = min(d[i+1][j+1], d[i][j] + 1)

otherwise 


d[i+1][j] = min(d[i+1][j], d[i][j] + 1) and d[i][j+1] = min(d[i][j+1], d[i][j] + 1);

if transition in d is optimal (that means d[i+1][j] = d[i][j] + 1 and others), add ways to dp (dp[i+1][j] += dp[i][j] and others)

→ Ответить