I'm looking for an algorithm to find the longest prefix of a certain string. This is not longest common substring (not directly anyways).
For example, for the strings
string1 = "01234567"
string2 = "12345601"
it should return "01", because I only want substrings in string2 that are a prefix of string1.
I think I've seen this somewhere before, but I can't remember the name of the algorithm I'm looking for.
I can just loop through string1 and find all the substrings in string2 of "0", "01", "012", "0123", etc.. and choose the longest one, but I'm wondering if there's something faster.
Does anyone know if there's a name for this algorithm?
I need to do this as part of a LZ77 compression algorithm implementation.
when you find "0" - you can check the next chars - you'll validate "01" without searching it...
next char will be different, so "012" you'll search using strstr again, if found - check '3', '4' etc till the end of the suitable substring