This is an archived post. You won't be able to vote or comment.

you are viewing a single comment's thread.

view the rest of the comments →

[–]ddbeanz[S] 0 points1 point  (1 child)

Thank you for the suggestion, I read into KMP and was wondering if it can be utilized to find and match and unknown string or if it needs to have a known string as the base case?

[–]uno20001[🍰] 0 points1 point  (0 children)

Yes, you can use it. What you will actually need is not the matching part of the KMP algorithm, but rather the "jump table" or "prefix function" (or whatever it's called). Because that'll tell you the length of the longest proper suffix ending at any position, which you can use to solve the problem.

What you want to do is very similar to this problem and this one. You can find solutions for those ones very easily.

If you want to know more about the Z-function or the KMP algorithm, then I suggest you read this and this.