Algorithm for string with one mismatch

Question

Could someone suggest a better approach for a string comparison among two strings with atmost one mismatch.

Example:

A: abcdefghabX
B: abc
Output: 1 9

The above outputs are the positions of substring matches of abc in "A"

I tried the basic approach with two for loops but, it seems to be taking N*N time. This is a big factor for large inputs and is taking huge amount of time.

My algorithm is as such but, it isn't a best one for huge amount of data

int compare(string a,  int pos, string b)
{
    int count = 0;
    int length = b.length()-1;
    int mid = b.length() /2;

    if(pos+length >= a.length())
        return 0;
    if((length+1)%2 != 0)   {
        for(int i=0,j=pos;i<=mid;i++,j++)   {       
            if(i == mid)    {
                if(a[j] != b[i])
                    count ++;
            }
            else    {
                if(a[j] != b[i])
                    count ++;
                if(a[pos+length - i] != b[length -i]) 
                    count ++;
            }
            if(count >= 2) return 0;
        }
    }
    else    {
        for(int i=0,j=pos;i<mid;i++,j++)    {       
            if(i == mid)    {
                if(a[j] != b[i])
                    count ++;
            }
            else    {
                if(a[j] != b[i])
                    count ++;
                if(a[pos+length - i] != b[length -i]) 
                    count ++;
            }
            if(count >= 2) return 0;
        }
    }
    return 1;
}

stark · Accepted Answer · 2012-02-24 00:54:05Z

3

What you want is implemented in agrep, so have a look at the algorithms it uses.

answered Feb 24, 2012 at 0:54

stark

13.3k3 gold badges39 silver badges56 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Joel · Accepted Answer · 2012-02-24 01:33:24Z

2

I think what you're after is the Boyer-Moore algorithm.

Specifically, the approximate version here.

edited Feb 24, 2012 at 1:33

answered Feb 24, 2012 at 1:27

Joel

5,6741 gold badge23 silver badges19 bronze badges

1 Comment

Rama Over a year ago

Thanks Joel... That helped a lot.

Collectives™ on Stack Overflow

Algorithm for string with one mismatch

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related