Home > Articles, Data Structures & Algorithms > Implementation of string search algorithm.

Implementation of string search algorithm.

The following program finds all the occurrences of a word in a text string. We set the text string as an array of characters of fixed size (although we could, instead, use the operator ‘new’) and read it from the standard input using the function cin.get(). The memory allocation for the word entered in the command line and passed on as argument is done by the system before this program is called and we find the pointer to the string in argv[1]. For every starting position i in the array a, tries to associate the substring starting from this position with the p, checking character by character for equality. Each time we reach the end of p successfully, we display the starting position (i) of the word in the text on the screen.

You should know that the implementation of the algorithm does not take into account issues of data input validation or proper management of dynamic memory (e.g. avoiding memory leaks) because it is only necessary to highlight the logic of the algorithm.

#include <iostream>
#include <cstdlib>
#include <string>

using namespace std;

const int N = 10000;

int
main (int argc, char *argv[]) {
  int i; char t, a[N], *p;

  if (!argv[1])
    return EXIT_FAILURE;

  p = argv[1];

  for (i = 0; i < N-1; a[i] = t, i++)
    if (!cin.get (t))
      break;

  a[i] = 0;

  for (i = 0; a[i] != 0; i++) {
    int j;

    for (j = 0; p[j] != 0; j++)
      if (a[i+j] != p[j])
        break;

    if (!p[j])
      cout << i << " ";
  }

  cout << endl;

  return EXIT_SUCCESS;
}
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: