CODEWITHSUNDEEP
stringc++11
xprilion
xprilion

Reputation: 589

Is my string match algorithm fast?

I came up with this algorithm for matching exact strings after I tried understanding the ones already on the internet and terribly failing :P Can anyone please tell me if this is fast or slow as compared to pre-existing algorithms?

#include <iostream>
#include<cstring>

using namespace std;

int main(){

int i=0;
int j=0;
int foo=0;

string str;
string needle;

cin>>str;
cin>>needle;

int * arr = NULL;
int * arr2 = NULL;
int * match = NULL;

arr = new int [str.length()];

int x=0, y = 0, z = 0;
int n=0; char a, b;

cout<<"\nStep 1: ";

for(i=0;i<str.length();i++){
    if(str[i]==needle[0]){
        arr[x]=i; x++;
        cout<<i<<" ";
    }
}

arr[x]=str.length(); x++; cout<<"\nStep 2: ";

if(x){
    arr2 = new int [x];

    for(i=0;i<x-1;i++){
        if(arr[i+1]-arr[i]>=needle.length()){
            arr2[y]=arr[i]; y++;
            cout<<arr[i]<<" ";
        }
    }

    delete[]arr; cout<<"\nStep 3: ";

    if(y){
        match = new int [y];
        for(i=0;i<y;i++){
            n=arr2[i];
            for(j=0;j<needle.length(); j++){
                a=str[n+j]; b=needle[j];
                if(a==b){
                    foo=1;
                }
                else{
                    foo=0; break;
                }
            }
            if(foo){
                match[z]=n; z++;
                cout<<n<<" ";
            }
        }

        delete[]arr2;

        if(z){

        cout<<"\n\nMatches: ";
          for(i=0;i<z;i++){
            cout<<match[i]<<" ";
          }
        }
    }
  } 
return 0;
}

Upvotes: 0

Views: 51

Answers (2)

kaikadi-bella
kaikadi-bella

Reputation: 121

You can't use it like this:

arr = new int [str.length()]

It will give you a compile time error. But you can use that in Java.

Upvotes: -1

Stephen C
Stephen C

Reputation: 718826

"Can anyone please tell me if this is efficient enough ..."

No, because you haven't described the context in which the method is going to be used. In some cases, it will definitely be efficient enough. In others, probably not.

This is not intended to be a facetious answer. There is a real point:

Efficiency is rarely a goal in its own right, and in most cases the efficiency of particular section of code has little real significance in real world programming.

It is generally better to write simple, correct code, and only worry about the micro-level efficiency when you have measured the performance and profiled the application to identify the hotspots.

Now if you are interested in the performance of String search algorithms for its own sake, then I suggest you start by looking at this Wikipedia article which summarizes (and links to) a number of advanced string search algorthms.

Upvotes: 3

Related Questions