SHOBHIT-Improved String Search Algorithm

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

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

The main reason for publishing this new algorithm is, there was bug in my last search algorithm SHOBHIT-Advance String Search Algorithm . That bug had been raised by my blog follower.

I would like to give thanks to that guy.

My new algorithm is faster than the previous one.

PESUDOCODE OF ALGORITHM:

 Shobhit_Improved_String_Search(text, text_len, substr, substr_len)

 {

         If substr_len is greater than text_len

                return -1      

                       

         sub_end = substr_len -1

                       

         if substr_len is even

         then

                  sub_mid1 = (substr_len /2 ) – 1

                  sub_mid2 = (substr_len/2)

         else

                  sub_mid1 = (substr_len/2)

                  sub_mid2 = (substr_len/2)

          sub_start = 0

          t_end = sub_end

          t_mid1 = sub_mid1

          t_mid2 = sub_mid2

          m1 = sub_mid1

          m2 = sub_mid2

          index=-1

          for ( t_start = 0;  t_end < text_len; t_start ++)

          {

                 If text[t_start] is equal to substr[sub_start] AND

                             text[t_end] is equal to substr[sub_end]

                  then

                          if index is equal to -1

                          then

                                index = t_start

                                               

                                if  ( sub_start + 1 is equal to sub_mid1 AND

                                                 sub_mid2 +1 is equal to sub_end )

                                         OR

                                    ( sub_start is equal to sub_mid1 AND

                                                 sub_mid2 is equal to sub_end )

           

                                then

                                         return index;           //Pattern Found

                                   

                                if text[t_mid1] is equal to substr[sub_mid1] AND

                                              text[t_mid2] is equal to substr[sub_mid2]

                                then

                                        increment sub_start by 1

                                        decrement sub_end by 1

                                         decrement sub_mid1 by 1

                                         increment sub_mid2 by 1

                                         decrement t_end by 1

                                         decrement t_mid1 by 1

                                         increment t_mid2 by 1

                                else

                                         set sub_start to zero

                                         set sub_end to substr_len -1

                                         set sub_mid1 to m1

                                         set sub_mid2 to m2

                                         set t_end to t_start + sub_end + 1

                                         set t_mid1 to sub_mid1 + t_start + 1

                                         set t_mid2 to sub_mid2 + t_start + 1

                                         set index to -1

                     else

                               set sub_start to zero

                               set sub_end to substr_len -1

                               set sub_mid1 to m1

                               set sub_mid2 to m2

                               set t_end to t_start + sub_end

                               set t_mid1 to sub_mid1 + t_start

                               set t_mid2 to sub_mid2 + t_start

                               set index to -1

                                   

                               If text[t_start] is equal to substr[sub_start] AND

                                         text[t_end] is equal to substr[sub_end]

                                then

                                         if index is equal to -1

                                         then

                                               index = t_start

                                               

                                          if  ( sub_start + 1 is equal to sub_mid1 AND

                                                            sub_mid2 +1 is equal to sub_end )

                                                 OR

                                                  ( sub_start is equal to sub_mid1 AND

                                                             sub_mid2 is equal to sub_end )

           

                                           then

                                                  return index;           //Pattern Found

                                   

                                          if text[t_mid1] is equal to substr[sub_mid1] AND

                                                         text[t_mid2] is equal to substr[sub_mid2]

                                          then

                                                increment sub_start by 1

                                                decrement sub_end by 1

                                                decrement sub_mid1 by 1

                                                 increment sub_mid2 by 1

                                                 decrement t_end by 1

                                                 decrement t_mid1 by 1

                                                  increment t_mid2 by 1

                                                           

                            else

                                   increment t_end by 1

                                   increment t_mid1 by 1

                                   increment t_mid2 by 1

                                                           

 }

TIME and SPACE Complexity:

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

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

In all the cases best, average and worst its space complexity is O(1).

This algorithm checks four 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/4 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 source code from the following link.

SHOBHIT-Improved String SearchAlgorithm source code. 

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 drop me a mail at < sho.upadhyaya@gmail.com > or do comment on my blog.

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.

      SHOBHIT-Advance String Search Algorithm in Graphical Way

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.

SHOBHIT-AdvanceString Search Algorithm source code.

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.

http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/StringMatch/kuthMP.htm

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)

http://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm

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)

http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm

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

SHOBHIT-Advance String Search Algorithm in Graphical Way

SHOBHIT-Advance String Search Algorithm in Graphical Way

back to main page of Algorithm

How to create Theme for Google Chrome

Hello Friends,

            Today we are going to learn “How we can create Theme for Google Chrome”

I have already created a demonstration theme for you guys. I hope you will like that.

FirstLove Theme:-

https://www.mychrometheme.com/t/ct6z4n0ag3ibfz5x7xex0i4k4    

           

Create a theme for Google Chrome is very easy, you just need to follow the following steps:-

Step 1:-         Add My Chrome Theme

                       

First of all you need to add My Chrome Theme into your Google Chrome.

Copy and Paste the following link into your chrome address bar.

             https://chrome.google.com/webstore/detail/my-chrome-theme/oehpjpccmlcalbenfhnacjeocbjdonic/related?hl=en

This link will take you to the My Chrome Theme app.

Now click on the Add to Chrome button.

Step 2:-         Launch My Chrome Theme

            After adding it you need to launch My Chrome Theme. After Launch My Chrome Theme will look like as follows:-

            

            Click on the Start Making Theme button

Step 3:-         Choose an Image for the Background

            Upload an image for the background of your theme.

            You can also take it from your webcam.

Step 4:-         Adjust Position / Image Effects

           

            You can also adjust the position of the uploaded image. There are some image effects also. You can use these effects too.

            Click on the Continue to Step 2 button.

Step 5:-         Color your Theme

                       

            You can color your Toolbar Color, Background Tab Color and Frame Color.

            You can also use the I’m Feeling Lucky button. That selects all the colors automatically.

            After color selection click on the Continue to Step3 button.

Step 6:-         Make my Theme

           

            In this step you can give the name of your theme. If you want you can add some more description about your theme.

            After mentioning the name and description click on the Make my Theme button.

Step 7:-         Final Step

           

            Congratulation you have successfully created your first theme.

            You can install your theme or if you want to share with your friends you can do that in this stage.

Please give your suggestion and feedback. If you have any doubts please feel free to ask…

C++ 11 Tutorial

Hello Friend,

            This is the index page of C++ 11.

This page maps the topic covered by the C++11 Tutorial.

        1.     What is auto and decltype, how to use?

        2.     What is nullptr and enum classes, how to use?

        3.     What is range based for statements and override virtual methods, how to use?

        4.     What is lambda function and how to use?

        5.     What is static assert and type_traits and how to use?

LIFECYCLE of an ACTIVITY (Part 3)

Hello friends,

            Welcome you all in the “LIFECYCLE of an Activity” part 3.

In the part2 we have learnt, how to use onCreate(), onStart() and onResume() system call. We have also seen how the Activity comes into RESUME (visible) state.

Click the following link to refer:-

            LIFECYCLE  of an Activity [Part 2]

            LIFECYCLE  of an Activity [Part 1]

In this part3, we will learn, how to use onPause(), onStop() and onDestroy() system call. We will also learn how state change from RESUME to PAUSED, PAUSED to STOP and STOP to DESTROY.

Step1:            User Interface of MainActivity

                        Add one more Button into the MainActivity name as “Start Sub Activity”.

                        Please add the following code into the activity_main.xml file.

Step2:            Create a New Activity

                        File à New à Other à Android à AndroidActivity

                        Select BlankActivity, click Next.

                        Project:         LifeCycleDemo                   

                        Activity name:  SubActivity

                        Click Finish.

Step3:            Implement onPause(), onStop(), onDestroy() system calls

Define the onPause(), onStop() and onDestroy() system call into the MainActivity.

Create a function that handles the “Start Sub Acivity” Button click event.

Please add the following code into the MainActivity.java file:-

          @Override
   protected void onPause() {
        super.onPause();
        mStatusView.append("MainActivity: onPause()\n");
        mStatusView.append("MainActivity: In PAUSED state ---\n");
         
   }
 
          @Override
   protected void onStop() {
        super.onStop();
        mStatusView.append("MainActivity: onStop()\n");
        mStatusView.append("MainActivity: In STOP state ---\n");
   }
  
   @Override
   protected void onDestroy() {
        super.onDestroy();
        mStatusView.append("MainActivity: onDestroy()\n");
          
       }

      public void startSubActivity(View v) 
         {
         Intent intent = new Intent(MainActivity.this, SubActivity.class);
  startActivity(intent);
         }

Step4:            Implement all the lifecycle system calls for SubActivity

                      Please modify the SubActivity.java file as follows:-

 package com.example.lifecycledemo;

 import android.os.Bundle;
 import android.app.Activity;
 import android.view.Menu;
 import android.view.View;
 import android.widget.TextView;

 public class SubActivity extends Activity {

  private TextView mStatusView;
  @Override
  protected void onCreate(Bundle savedInstanceState) {
   super.onCreate(savedInstanceState);
   setContentView(R.layout.activity_sub);
   mStatusView = (TextView) findViewById(R.id.status_current);
   mStatusView.setText("SubActivity: onCreate()\n");
  }

  @Override
  public boolean onCreateOptionsMenu(Menu menu) {
 // Inflate the menu; this adds items to the action bar if it is present.
   getMenuInflater().inflate(R.menu.activity_sub, menu);
   return true;
  }

  protected void onStart() {
   super.onStart();
   mStatusView.append("SubActivity: onStart()\n");
  }
  protected void onResume() {
   super.onResume();
   mStatusView.append("SubActivity: onResume()\n");
   mStatusView.append("SubActivity: In RESUME state ---\n");
  }

  @Override
  protected void onPause() {
   super.onPause();
   mStatusView.append("SubActivity: onPause()\n");
   mStatusView.append("SubActivity: In PAUSED state ---\n");

  }
  @Override
  protected void onStop() {
   super.onStop();
   mStatusView.append("SubActivity: onStop()\n");
   mStatusView.append("SubActivity: In STOP state ---\n");
  }

  @Override
  protected void onDestroy() {
   super.onDestroy();
   mStatusView.append("SubActivity: onDestroy()\n");

  }

  public void destroyActivity(View v) {
   SubActivity.this.finish();
  }
 }

Step 5:           Design User Interface for SubActivity

Please modify the activity_sub.xml file as follows:-

Step 6:           Compile and RUN the application.

Visible state of MainActivity :-

Click the Start Sub_Activity Button, Now the State of MainActivity and State of SubActivity are as follows:-

 

Destroy the SubActivity:-

Please give your valuable comments.

Do not forgot to share !!!

LIFECYCLE of an ACTIVITY (Part 2)

Hello friends,

            Welcome you all in the “LIFECYCLE of an Activity” part 2.

In the part1 we have learnt, what is an Activity and its Lifecycle?

           

In this part2, we create a lifecycle demo application, which demonstrate how the state of an Activity changes?

This application also demonstrates what are the system call invoke when an Activity changes the State.

Step1:-          Create an Android Application Project

                       

                        First of all create a new Project.

                        File à New à Android Application Project

                                    Application Name: LifeCycleDemo

                        Click Next

                        Click Next

                        Select BlankActivity, Click Next

                        Click Finish

Step2:-          Create User Interface

We are using the LinearLayout and vertical orientation for this applicaton.
 We need to set this in activity_main.xml file.

We are also putting some TextView and Button in our demo application to make it user interactive.

Modify the activity_main.xml with the following code:-

Step 3:-         Modify the strings.xml file

                        Please copy-paste the following code into the strings.xml file.

 
 

     LifeCycleDemo
     Hello world!
     Settings
     Start [ Sub_Activity ]
     Destroy Current Activity
     Status
     SubActivity

 

                       

Step 4:-         Defining color and fonts for the application.

           

                        Go to /res/values directory of the LifeCycleDemo project.

                        Create a new xml file and give name as color_and_font.xml

 
 
     #FFFFFF
     #000000

     #A8DFF4
     #D3E992
     #FFAFAF
     #FFECC0

     #0099CC
     #669900
     #CC0000
     #FF8A00

     44dp
     24dp
     10dp

 

                       

Step 5:-         Defining system calls, who changes the State of an Activity.

                        Please modify the MainActivity.java file with the following code:-

   
 package com.example.lifecycledemo;

 import android.os.Bundle;
 import android.app.Activity;
 import android.content.Intent;
 import android.view.Menu;
 import android.view.View;
 import android.widget.TextView;

 public class MainActivity extends Activity
 {

  private TextView mStatusView;
  @Override
  protected void onCreate(Bundle savedInstanceState) {
   super.onCreate(savedInstanceState);
   setContentView(R.layout.activity_main);
   mStatusView = (TextView) findViewById(R.id.status_current);
   mStatusView.setText("MainActivity: onCreate()\n");
  }
  protected void onStart() {
   super.onStart();
   mStatusView.append("MainActivity: onStart()\n");
  }
  protected void onResume() {
   super.onResume();
   mStatusView.append("MainActivity: onResume()\n");
   mStatusView.append("MainActivity: In RESUME state ---\n");
  }


  @Override
  public boolean onCreateOptionsMenu(Menu menu) {
   // Inflate the menu; this adds items to the action bar if it is present.
   getMenuInflater().inflate(R.menu.activity_main, menu);
   return true;
  }

  public void destroyActivity(View v) {
   MainActivity.this.finish();
  }



 }

                       

Step 6:-         Compile and RUN the LifeCycleDemo application.

This application shows you, when onCreate(), onStart(), onResume()  system call invoke and How the application came into RESUME (visible) state.

In the next part we will see, How the application move into the PAUSED, STOP and DESTROY state?