Thread: longest prefix

  1. #1
    Registered User
    Join Date
    Feb 2005

    longest prefix


    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.


  2. #2
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Rishon LeZion, Israel
    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
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    David J. Wheeler

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Longest and Shortest String
    By dnguyen1022 in forum C++ Programming
    Replies: 40
    Last Post: 01-31-2009, 09:08 PM
  2. Replies: 7
    Last Post: 11-25-2008, 01:50 AM
  3. Atomic Operations
    By Elysia in forum Windows Programming
    Replies: 27
    Last Post: 03-27-2008, 02:38 AM
  4. longest common substring problem
    By Enchanter88 in forum C++ Programming
    Replies: 4
    Last Post: 09-29-2007, 11:02 AM
  5. using strlen and finding shortest and longest words
    By Unregistered in forum C Programming
    Replies: 7
    Last Post: 09-30-2001, 06:09 PM