Help me out in this

#1
#2

hello @shivammishra20121999

try to do it using any string matching algorithm

#3

@aman212yadav can you tell me how to approach in terms of logic?

#4

@aman212yadav i am trying to do this with kmp but unable to crack its logic??

#5

pls refer this->link

#6

@aman212yadav can you explain the logic i am not getting??

#7

i need to solve it first to explain u .
that might take some time. till then try on ur own

#8

@aman212yadav okay bro

#9

@shivammishra20121999

first use kmp to find prefix which is also suffix i.e prepare lps array . (say p).
If i mod (i - p[i]) == 0 then K = i / (i - p[i]) else K = 1.

how i-p[i] will be period?
Suppose that x is a string of length n. To find the period of x, compute the KMP prefix function of x. The period of x is n - p(n). This is because a periodic string with period k matches itself when shifted forward k characters. So the length n-k prefix of the string must be identical to the length n-k suffix.

the whole idea is inspired from this problem -> link

#10

@aman212yadav
a a b a a b a a b a a b
lps 0 1 0 1 2 3 4 5 6 7 8 9
can you explain with this example?

#11

bro check the link i shared, example is given with explanation.

#12

@aman212yadav okay bro

#13

is this clear now?. .

#14

@aman212yadav thks bro got cleared i know you say please marked it resolved

#15

lol, but mein to aisa kabhi nahi kehta hun
mein to bus puch raha tha ki aaya samjh mein ya nahi.

#16

@aman212yadav okay i am kidding bro this question is good very much intuitive very good question for kmp

#17

yeah it was a good question.
and yeah the whole idea was how u compute period for given string .
period -> n - lps[n] (keep this in mind, can be helpful in verious other string related problems)

#18

@aman212yadav okay bro

#19

@aman212yadav n-lps[n]*k = n if this hold then n-lps[n] is it s peroid
that is logic here

#20

u mean n % (n-lps[n]) = 0 right? for n-lps[n] to be its period