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

Another ad-hoc string problem
Автор glow, история, 6 лет назад, По-английски

A string is called beautiful if string S = T + T. You're given a string find length of longest beautiful subsequence in given string.

Constraints : 1 <= length(S) <= 100

PS: Ihave no clue except try all numbers with k bits set and like bit-mask check if it's beautiful. Of-course you take k even and start from biggest possible k ie. length(S) - (length(S) & 1). Any hints on this ?

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

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

Main observation is: all letters of first part will be located earlier than any letter of second part.

Let's we fixed k as first index where only letters from second part could be. Now dynamic programming could be used:

dp[i][j] — maximal length of beautiful subsequence where first part ends in i (or earlier) and second in j (or earlier) (1 ≤ i < k ≤ j ≤ n).

This dp could be calculated in O(|S|2):

  • dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
  • if s[i] = s[j]: dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1).

Total complexity of solution is O(|S|3) that should easily fit with |S| ≤ 100.

→ Ответить
  • »
    »
    6 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    That's just came to my mind while I was relaxing a while ago.. dayummmmnn... In other words keep left rotating a copy of original string and for every left rotation find LCS, update answer with ans = max(ans,current_LCS/2)

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

      Maybe I misunderstood you, but maximal LCS of string S and any of its rotations has length |S| - 1 ('abcde' and 'bcdea').

      Main idea is separate two parts of answer in one string.

      → Ответить