Lintcode: strStr

strstr (a.k.a find sub string), is a useful function in string operation. Your task is to implement this function.

For a given source string and a target string, you should output the first index(from 0) of target string in source string.

If target does not exist in source, just return -1.

Have you met this question in a real interview? 

Yes

Example

If source = "source" and target = "target", return -1.

If source = "abcdabcdefg" and target = "bcd", return 1.

Challenge

O(n2) is acceptable. Can you implement an O(n) algorithm? (hint: KMP)

Clarification

Do I need to implement KMP Algorithm in a real interview?

• Not necessary. When you meet this problem in a real interview, the interviewer may just want to test your basic implementation ability. But make sure your confirm with the interviewer first.

This problem is a typical string search problem.
Brutal force solution:
We generally solve it with two loops.
O(n*n)
http://bangbingsyb.blogspot.com/2014/11/leetcode-implement-strstr-kmp.html

TIP: When assigning a constant pointer to a new variable, this variable has to be a constant pointer, too. Which guarantees that user cannot change the variable through the constant pointer.
参考 常量指针 与 指针常量 的区别

strlen() don't accept null as input, so we need to exclude these two situations

Initial version:

class Solution {
public:
    /**
     * Returns a index to the first occurrence of target in source,
     * or -1  if target is not part of source.
     * @param source string to be scanned.
     * @param target string containing the sequence of characters to match.
     */
    int strStr(const char *source, const char *target) {
        if(!target || !source) return -1; //when null
        if(!*target) return 0; //when ""
        int slen = strlen(source);
        int tlen = strlen(target);
        for(int i = 0; i < slen - tlen - 1; i++){
            const char *p1 = source + i;
            for(int j = 0; j < tlen; j++){
                const char *p2 = target + j;
                if(*p1++ != *p2) break;
                if(j == tlen - 1) return i;
            }
        }
        return -1;
    }
};

Modified version:

class Solution {
public:
    /**
     * Returns a index to the first occurrence of target in source,
     * or -1  if target is not part of source.
     * @param source string to be scanned.
     * @param target string containing the sequence of characters to match.
     */
    int strStr(const char *source, const char *target) {
        if(!target || !source) return -1; //when null
        if(!*target) return 0;  //when ""
        int slen = strlen(source);
        int tlen = strlen(target);
        for(int i = 0; i < slen - tlen - 1; i++){
            for(int j = 0; j < tlen; j++){
                //const char *p1 = source + i + j;
                //const char *p2 = target + j;
                if(source[i + j] != target[j]) break;
                if(j == tlen - 1) return i;
            }
        }
        return -1;
    }
};

KMP algorithm is O(n).
KMP WIKI
KMP好的讲解


Boyer-Moore WIKI