Harvest Software - Programming - Algorithm - Naive String Matching Algorithm

C/C++
Algorithm
Data Structure
UVA Hints
UVA Problem Ranking
Tip and Trick

Naive String Matching Algorithm

Problem Description
Given a string P,T. We want to check whether P is a substring of T.

Algorithm
As the name suggest, this algorithm search checks for all position i whether T is a substring of P.It uses a loop that checks the condition P[0..m-1] = T[i..i+m-1]. Let n = length(T) and m = length(P) so the complexity of this algorithm is O( (n-m+1)*m )

Implementation in C/C++

/* Naive Strint Matching Algorithm
    strMatch(T,P)
    - match whether P is substring of T
    - return the starting index of the first occurence of P in T
*/


#include <cstdio> // #include <stdio.h>

int strMatch(char *T,char *P)
{
    int i,j,n,m,found;
    n = strlen(T);
    m = strlen(P);
               
    for (i=0; i<=n-m; i++)
    {
        found = 1;
        for (j=0; j<m; j++)
           if (P[j] != T[i+j])
           {
               found = 0;
               break;
           }
        if (found) return i;
    }
    return -1;
}