How to solve this question.

general
, , , , ,
1

How to solve this question ?

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

Thanks.

2

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–;
}
}
}

3

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

4

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.