Thread: Got better algorithm instead of while loop?

  1. #1
    Registered User
    Join Date
    Dec 2004
    Posts
    163

    Got better algorithm instead of while loop?

    I got an array that store the position of the characters in a string and they are stored in their ASCII character order, using Counting Sort algorithm.

    For example, with a string ABABAC, the the first position is 0,
    the array is stored as this order:

    0,2,4,1,3,5
    where 0,2,4 are A, 1,3 are B and 5 is C.

    I then use this array to check if there is common pattern among the characters.

    I use a while loop, since I know 0 and 2 are A, I increment their pointers to 1 and 3. I compare 1 with 3, they have same characters. I increment the pointers again. 2 compare with 4, they have different characters. Thus, I know there exist a common pattern AB.

    After this, I use 0 to compare with 4 again, to check for common pattern.

    But this way of doing while loop is not efficient. Is there any other algorithms that is faster?

    Thanks for your help!

  2. #2
    ---
    Join Date
    May 2004
    Posts
    1,379
    Why dont you show me some code to make it easier.

  3. #3
    Registered User
    Join Date
    Dec 2004
    Posts
    163
    sure, this is the main function that is doing the work, and there is some subfunctions that I didn't place, because the codes are too long. What I am seeking for is if there is any algorithms that do this? (the function is described in my previous message)

    For e.g. in sorting, there are insertion sort, counting sort, bubble sort, etc.... so is there any good algorithms that do the same task as mine?

    Code:
    void NormalSituation(unsigned char *str, unsigned int *suffixes, unsigned int rightboundary, unsigned int *LCP, CommonPatternPtr *cp, CommonPatternPtr *tailPtr, unsigned int j, unsigned int filelength)
    {
      unsigned int tempLCP, LCPlength;
      int k=0,i;
      k = rightboundary;
      while ((*LCP==0) && (j!=k))
        {
          if (GetReadBit(&str[suffixes[k]]) && GetReadBit(&str[suffixes[k]-1]))
    	{
    	  if ((suffixes[j] != (suffixes[k] - 1)))
    	    {
    	      tempLCP =  FindLCP(str, suffixes, j, k, filelength);
    	      if (tempLCP>*LCP)
    		{
    		  *LCP = tempLCP;
    		  NewLCPParameters(LCP, tempLCP,j, k, cp, tailPtr, suffixes);      	   	
    		}
    	    }
    	}
          k--;
        }
      if (*LCP > 0)
        {
          for (i=k; i>j; i--)
    	{ 
    	  if (GetReadBit(&str[suffixes[i]]) && GetReadBit(&str[suffixes[i]-1]))
    	    {
    	      if ((suffixes[j] != (suffixes[i] - 1)))
    		{
    		  LCPlength =  FindLCP2(str, suffixes, j, i, filelength, tempLCP);
    		  if (LCPlength == *LCP) //exist a CP node with the same LCP
    		    AddLCPParameters(LCP, tempLCP, i, cp, tailPtr, suffixes);        
    		}   
    	    }
    	} 	    
          AddLCPParameters(LCP, tempLCP,j, cp, tailPtr, suffixes);        
          SetReadBit(tailPtr, str, suffixes);
        }
    }

  4. #4
    Registered User lobo's Avatar
    Join Date
    Oct 2001
    Posts
    71
    Take a look here, it migh help you a bit..

    http://www.nist.gov/dads/HTML/stringMatching.html

    Simple extension of provided algorithm will solve your problem in additional O(n*n), but i'm pretty sure it can be done at least an O(n) faster, though

  5. #5
    Registered User
    Join Date
    Dec 2004
    Posts
    163
    Yo!

    That's a very useful link! Thanks man! Really appreciate it!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Visual Studio Express / Windows SDK?
    By cyberfish in forum C++ Programming
    Replies: 23
    Last Post: 01-22-2009, 02:13 AM
  2. Replies: 8
    Last Post: 12-01-2008, 10:09 AM
  3. return to start coding?
    By talnoy in forum C++ Programming
    Replies: 1
    Last Post: 01-26-2006, 03:48 AM
  4. when a while loop will stop ?
    By blue_gene in forum C Programming
    Replies: 13
    Last Post: 04-20-2004, 03:45 PM
  5. How to change recursive loop to non recursive loop
    By ooosawaddee3 in forum C Programming
    Replies: 1
    Last Post: 06-24-2002, 08:15 AM