You are not logged in. Please login at www.codechef.com to post your questions!

×

How to solve this question.

How to solve this question ?

Can anyone please tell me approach based on z-algorithm for above question ??

Thanks.

asked 22 Jun '15, 14:34

glow's gravatar image

3★glow
6312
accept rate: 0%

edited 02 Jul '15, 12:50


Simple and short. Note that the optimization L = R = i is used when S[0] ≠ S[i] (it doesn't affect the algorithm since at the next iteration i > R regardless).

int L = 0, R = 0; for (int i = 1; i < n; i++) { if (i > R) { L = R = i; while (R < n && s[R-L] == s[R]) R++; z[i] = R-L; R--; } else { int k = i-L; if (z[k] < R-i+1) z[i] = z[k]; else { L = i; while (R < n && s[R-L] == s[R]) R++; z[i] = R-L; R--; } } }

link

answered 22 Jun '15, 18:11

bikashsingh's gravatar image

2★bikashsingh
152
accept rate: 0%

This is actual z-algo code, i want to know how to use z-algo to solve this question ? Can somebody please help ?

(24 Jun '15, 21:40) glow3★

now i've got an idea how to solve it using Z-algo here is the code http://ideone.com/Ddnf36 but in this one didnt get accepted, the problem is that when we find the 'match' string we need to decrease its size and compare at both ends untill size of match reduces to zero ... but i think that its not a good strategy to do that.. so now can anyone guide to optimise the code..??

MY_Approach : compute Z-values now store value and indexes of top two elements let top values be maxi and maxii , and their indexes be first,second repectively now start from first till maxii's length(means maxii times) now this is match string now just compare it at both ends if no match at any end than keep decreasing till its both end match or size becomes zero.

Thanks.

link

answered 25 Jun '15, 22:57

glow's gravatar image

3★glow
6312
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,657
×2,212
×688
×74
×41
×4

question asked: 22 Jun '15, 14:34

question was seen: 1,129 times

last updated: 02 Jul '15, 12:50