strStr

Description

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

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

Example

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

If source ="abcdabcdefg"and target ="bcd", return1.

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

Challenge

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

Related problems

strStr II

Implementation

Link: http://lintcode.com/en/problem/strstr/

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) {
        // write your code here
        if(source == NULL || target == NULL) return -1;

        // How about target == "" or source == ""

        //cout << "source len " << strlen(source) << " target len " << strlen(target) << endl;

        for(int i = 0; ;i++){
            for(int j = 0; ; j++){
                //cout << " i " << i << " j " << j << endl;
                if(j == strlen(target)) return i;
                if((i + j)  == strlen(source)) return -1;
                if(target[j] != source[i + j]) break;
            }
        }
    }

#if 0
    int strStr(const char *source, const char *target) {
        // write your code here
        if(source == NULL || target == NULL) return -1;
        if(strlen(target) > strlen(source)) return -1;

        for(int i = 0; i < strlen(source) - strlen(target) + 1; i++){
            int j = 0;

            for(j = 0; j < strlen(target); j++){
                if(target[j] != source[i+j]) break;
            }

            if(j == strlen(target)) return i;
        }

        return -1;
    }
#endif
};