negetive_iq's blog

Can someone help me with this problem C1. Message Transmission Error (hard version)?
By negetive_iq, history, 5 hours 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
  • 0
  • Vote: I do not like it

»
5 hours 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
»
5 hours 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
  • »
    »
    5 hours 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
    • »
      »
      »
      5 hours 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