negetive_iq's blog

Can someone help me with this problem C1. Message Transmission Error (hard version)?
By negetive_iq, history, 2 months ago, In English

I have solved the easy version of the problem. But I have no idea how to solve this one. Do I require any new algorithms? Can someone please help me solve this problem?

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by negetive_iq (previous revision, new revision, compare).

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Learn pattern searching algorithms like Z function, KMP, etc. I used Z function to solve this question.

→ Reply
  • »
    »
    2 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Can you explain a bit more in detail on how to solve this after learning pattern matching algorithms?

    → Reply
    • »
      »
      »
      2 months ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      The problem after this will turn into "for string $$$s$$$ of length $$$n$$$, find any index $$$i$$$ ($$$2 \le i \le n$$$) such as $$$s(i, n) = s(1, n-i+1)$$$ and $$$i \le n-i+1$$$".

      (Here, $$$s(i, j)$$$ means a contiguous substring of $$$s$$$ from index $$$i$$$ to index $$$j$$$, inclusively).

      → Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you give me the link to the problem?

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

To solve the problem, analyze the string t to determine if it can be the result of merging two identical consecutive messages. Compute the length of the longest prefix that is also a suffix of the string. If this length is at least half the length of t plus one, it indicates a possible merging error, and you should print "YES" along with the prefix. If not, print "NO". For this, you can use the KMP algorithm’s LPS (Longest Prefix Suffix) array to efficiently find the longest prefix which is also a suffix.

→ Reply