longest prefix

This is a discussion on longest prefix within the C Programming forums, part of the General Programming Boards category; Hi, I'm looking for an algorithm to find the longest prefix of a certain string. This is not longest common ...

  1. #1
    Registered User
    Join Date
    Feb 2005
    Posts
    46

    longest prefix

    Hi,

    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"
    and
    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.

    Thanks

  2. #2
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,424
    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
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

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, 08:08 PM
  2. Replies: 7
    Last Post: 11-25-2008, 12: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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21