Monday, 5 August 2013

SHOBHIT-Advance String Search Algorithm



In Computer Science, SHOBHIT-Advance String Search Algorithm is a string searching algorithm created by SHOBHIT UPADHYAYA in 2013. He is working as a Software Developer in Bangalore India.

“This algorithm uses the first and last index of the substring for a pattern search.”


PESUDOCODE OF ALGORITHM:

Shobhit_Advance_String_Search( str1 , length_of_str1, str2 , length_of_str2 )
{
      i =  0;
      j =  0;
      k = length_of_str2 -1
      last = length_of_str2 -1;
      index = -1
     
      if length_of_str2 is greater than length_of_str1
            return index

      for(  ; k is less than length_of_str1 ; increment i by one )
      {
           if str2[ j ] equals to str1[ i ] and str2[ last ] equals to str1[ k ]
           then
                   if index equals to -1
                         set index to i

                   if j equals to last or j + 1 equals to last
                   then
                            do break; // pattern found
                    else
                           increment j by one
                           decrement last by one
                            decrement k by one
         else
                 set index to -1
                 set j to zero
                 set last to length_of_str2 -1              
                 set k to i + last

                 if str2[ j ] equals to str1[ i ] and str2[last] equals to str1[k]
                 then
                            if index equals to -1
                                    set index to i

                            if j equals to last or j + 1 equals to last
                           then
                                    do break; // pattern found
                           else
                                    increment j by one
                                   decrement last by one
                                   decrement k by one
                 else
                          increment k by one
      }
      return index
}

 Please click on the following link to understand better this Algorithm.


TIME and SPACE Complexity:

For a text of length n and substring of length m.

Its best case, time complexity is O(m/2) and in worst case, time complexity is O(n – (m/2) ).

In all the cases best, average and worst its space complexity is O(1).
This algorithm checks two characters at a time.
In best case where the substring is at the start of the text, we can check all the character of substring in only m/2 time.
In worst case where the substring is at the last of the text, we need to iterate till n – m


SOURCE CODE AND LICENSE:-

          The code of this algorithm is free and it’s under

GNU GENERAL PUBLIC LICENSE

Version 3, 29 June 2007
Please find out the code from the following link.
The source code is having the algorithm api and a test application code to test the api.
If you found any bug or if you want to communicate related to this algorithm send me a mail < sho.upadhyaya@gmail.com > or do comment on my blog.

           

Other Good String Search ALGORITHM:-

1)     Knuth-Morris-Pratt Algorithm
The running time of Knuth-Morris-Pratt algorithm is proportional to the time needed to read the characters in text and pattern. In other words, the worst-case running time of the algorithm is O(m + n) and it requires O(m) extra space. It is important to note that these quantities are independent of the size of the underlying alphabet.

2)     Rabin-Karp Algorithm
 For text of length n and p patterns of combined length m, its average and best case running time is O(n+m) in space O(p), but its worst-case time is O(nm)

3)     Boyer-Moore String search  Algorithm
Worst Case runtime when pattern occur in the text is O(nm)
Worst Case runtime when pattern does not occur in the text is O(n+m)

4)     Aho-Corasick string matching algorithm
 Aho–Corasick string matching algorithm has asymptotic worst-time complexity O(n+m) in space O(m).
                                   

THANKS FOR READING