strStr

Description

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.

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.

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)

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

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 ( !target || !source ) {
            return -1;
        }
        if( strlen(target) == 0 ){
            return 0;
        }
        int n = strlen(source) - strlen(target) + 1;
        for(int i = 0 ; i<n; ++i){
            if(source[i] == target[0]){
                //test substr
                int j = 1;
                for( ; j < strlen(target); ++j ){
                    if( source[i+j] != target[j] ){
                        break;
                    }
                }
                // without break occurring
                if( j == strlen(target) ){
                    return i;
                }
            }
        }
        return -1;
    }
};

Similar problems

x

Tags

x