C program for naive string matching algorithm.

Posted by Mangesh on May 13, 2018

/* program for naive string matching. */

Description :

The idea of the naive solution is just to make a comparison character by character of the text T [ s...s + m − 1] for all s ∈ { 0 , . . . , n − m + 1 } and the pattern P [0 ...n − 1]. It returns all the valid shifts found. In fact, the time complexity of the Naive algorithm in its worst case is O ( M × N ). For example if the pattern to search is a n and the text is a m , then we need N operation of comparison by shift. For all the text, we need ( N − M + 1) × M operation, generally N is very small compared to M , it is why we can simply considered the complexity as O ( M × N ).

Program :

#include<stdio.h>
#include<conio.h>
#include<string.h>
void main()
{
  char str1[20],str2[20];
  int m,n,i,j;
  clrscr();

  printf("\nEnter text string : ");
  scanf("%s",&str1);

  printf("Enter pattern to search : ");
  scanf("%s",&str2);

  m = strlen(str1);
  n = strlen(str2);

  for(i=0;i<m-n+1;i++)
  {
    for(j=0;j<n;j++)
    {
     if(str1[i+j] != str2[j])
       break;
    }
    if(j == n)
    {
      printf("\n\n Pattern found at %d. ",i);
    }
  }
  getch();
}

Output :

c program for naive string matching algo Executed and tested in Turbo C 3.2

Written with from Mangesh.

Related Post
1 C program for naive string matching algorithm.
2 C program to check whether the given string is palindrome or not.
3 C program to concatenate two string.
4 C program to check whether two strings are anagram or not.
5 C program to reverse the string.
6 C program to replace a character in a string.
7 C program to compare two string.
8 C program to compare two string using strcmp function.
Latest Post
1 C program to implement Queue using linked list.
2 C program for binary search tree (BST).
3 C program to search an element in linked list.
4 C program for postorder traversal in binary tree.
5 C program for preorder traversal in binary tree.