LCS বের করার জন্য CORMEN এর Algorithm বই এ যে algorithm আছে তার time complexity O(n*m)। যদি string 2 টির size 10^12 হয় তাহলে programming contest এ এই algorithm ব্যবহার করা যাবে কি? এবং এর চেয়ে কম সময় এ run করে এরকম algorithm আছে কি?

asked 16 Oct '16, 13:47

Anisur%20Rahman%20Tonu's gravatar image

Anisur Rahman Tonu

Answering from programming contest perspective: Programming contest has limited time and resources. You can't possibly store a 10^12 length string on a typical workstation. You need distributed storage for that kind of memory. Reading such a huge file would take the whole contest to run. Apart from that regular LCS can't be solved in a better approach. Some optimization may be possible but they won't help such a large case.

From my experience i can tell you that such kind of problems have special conditions for generating the strings and solving the problem. So my advice would be to look for those special conditions and see how that can be feasible for you.

permanent link

answered 16 Oct '16, 14:28

nfssdq's gravatar image


Is it possible for length 10^5 ?

(16 Oct '16, 15:30) Anisur Rahman Tonu

No. At most 5K is feasible.

(16 Oct '16, 15:33) nfssdq

It would better help for me if you give a better algorithm for that. Thanks

(16 Oct '16, 15:49) Anisur Rahman Tonu

And also an example

(16 Oct '16, 15:50) Anisur Rahman Tonu
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Question tags:


question asked: 16 Oct '16, 13:47

question was seen: 672 times

last updated: 16 Oct '16, 15:50