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]
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
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
No comments:
Post a Comment