Microsoft Interview Question : Write an efficient string matching program for string matching ?

Question

Write a time efficient C program that takes two strings (string a, string b) and gives the first occurence of string b in string a.

Answer 1

Wikipedia knows all

Answer 2

Many algorithm is on string matching. For example,Knuth–Morris–Pratt algorithm, Boyer-Moore algorithm. Just refer to any one algorithm handbook.

Answer 3

Write an efficient C program that takes two strings (string a, string b) and gives the first occurence of string b in string a.

It doesnt say that you are doing repeated matching against either string, or any useful insight about one being particularly short, specific content, or there being plenty of startup time then a trigger event after which a fast-as-possible comparison is needed, so: all the sophisticated algorithms mentioned in other answers probably are not sought by the interviewer.

I read "efficient" to mean that the algorithm is not iterating and invoking an out-of-line strcmp(), mindful not to repeatedly call strlen(), preferably returns false immediately if the equality comparison exhausts "haystack" before "needle". Honestly, if it is an early screening interview, then enough people would fail to implement something like that well - it is very believable that that is all they wanted without going into advanced prior indexing or state machines.

Answer 4

I think the following should achieve what you intend to do -

int main(int argc, char *argv[]) {

string A, B;
size_t pos;

while (true) 
{
    cout << endl << "Enter string: ";
    getline(cin,A);
    cout << "Enter substring to find: ";
    getline(cin,B);
    if ((A.size() > 0) && (B.size() > 0)) 
    {
        cout << "\"" << B << "\" is";
        if ((pos = find(A,B)) == string::npos) 
        {
            cout << " not";
        }
        cout << " a substring of \"" << A<< "\"";
        if (pos != string::npos) 
        {
            cout << ", found at index " << pos;
        }
        cout << endl;
    }
}
return 0;

}

Answer 5

If you're interested, have a look at Michael Abrash's chapter(PDF) on string searching in his "Graphics Programming Black Book". The rest of the book can be freely accessed here.

He starts out with a nice routine in C, then improves it and implements it in assembly. Although not really in the scope of the interview question, I think most interviewers would be impressed with an explanation of how to optimise your answer.

Answer 6

The question doesn't specify a result for if B does not occur in A, nor does it require the position of the occurrence. So it is safe to assume that A contains B. Hence the program should return string B, as the value of the first occurrence of B in A will be equal to B.

I believe much of Windows NT's POSIX compliance was built on similar principles.