Jul 12, 2016

Find a substring in a string in O(n)

#include <stdio.h>

int substring(char* src, char *trg, int slen, int tlen)
{
    if(!src || !trg || !slen || !tlen)
        return -1;
   
    if(slen < tlen)
        return -1;
       
    int repeat = -1;
    for(int s=0,t=0; s< slen; s++)
    {
        if((src[s] == trg[0]) && (t!=0))
        {
            //repeat char found in src
            repeat = s;
            //printf("repeat pos %d\n", s);
        }

        if(src[s] == trg[t])
        {
            t++; //iterate to next target char
            if(t == tlen)
            {
                return s-t+1;    //index of src's first char matching with trg's first
            }
        }
        else
        {
            t=0;
            if(repeat != -1)
                s = repeat-1;
        }
       
    }
   
    return -1;
}

int stringlength(char *src)
{
    if(!src)
        return 0;
   
    int i;
    for(i=0; *src!='\0'; i++, src++)
        ;
   
    return i;
   
}

int main(void) {
   
    char bstr[] = "this is a bigbigbigstring";
    char sstr[] = "bigstr";
   
    int result = substring(bstr,sstr,stringlength(bstr),stringlength(sstr));
   
    printf("the index = %d", result);
    return 0;
}