LintCode 12. Implement strStr

DescriptionExampleChallengeSubmisson1. 穷举法（for循环）2. 穷举法（while，计数器）3. KMP算法（已补充）

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.

对于一个给定的 source 字符串和一个 target字符串，你应该在 source字符串中找出 target 字符串出现的第一个位置(从0开始)。如果不存在，则返回-1。

Example

Example 1:

Input: source = “source” ，target = “target” Output: -1 Explanation: If the source does not contain the target content, return - 1.

Example 2:

Input:source = “abcdabcdefg” ，target = “bcd” Output: 1 Explanation: If the source contains the target content, return the location where the target first appeared in the source.

Challenge

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

---

Submisson

1. 穷举法（for循环）

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 string &source, const string &target) { // write your code here int i, j; int len_source = source.length(); int len_target = target.length(); if(len_source == 0 && len_target == 0) { return 0; } if(len_source < len_target) { return -1; } for(i = 0; i <= len_source - len_target; i++) { for(j = 0; j < len_target; j++) { if(source[i + j] != target[j]) { break; } } if(j == len_target) { return i; } } return -1; } };

2. 穷举法（while，计数器）

class Solution { public: /** * @param source: * @param target: * @return: return the index */ int strStr(string &source, string &target) { // Write your code here int len_sou = source.length(); int len_target = target.length(); int i = 0; int j = 0; int cot = 0; while(cot < len_target && i < len_sou) { if(source[i] != target[j]) { j = -1; i = i - cot; cot = -1; } i++; j++; cot++; } if(cot == len_target || len_target == 0) { return i - cot ; } else { return -1; } } };

3. KMP算法（已补充）

class Solution { public: /** * @param source: * @param target: * @return: return the index */ vector<int> publicStr(const string &target) { // 寻找相同的前缀和后缀，用res数组记录 int len = target.length(); vector<int> res; // 第一组元素就一个字符，没有前缀和后缀 res.push_back(0); if(len == 1) { return res; } string start; string end1; string middle; int cot; int number; for(int k = 1; k < len - 1; k++) { // 依次进行寻找最大的共同字符（前缀==后缀） cot = 0; number = 0; for(int i = 0; i < k; i++) { middle = target.substr(0,k+1); start = middle.substr(0,i+1); end1 = middle.substr(k-i,i+1); if(start == end1) { number = i + 1; // 记录最长的字符长度 cot = max(cot,number); } } res.push_back(cot); } return res; } int strStr(string &source, string &target) { // Write your code here int len_source = source.length(); int len_target = target.length(); if(len_source == 0 && len_target == 0) { return 0; } if(len_source < len_target) { return -1; } vector<int> res = publicStr(target); int i = 0; int j = 0; while(i <= len_source - len_target && j < len_target) { if(source[i + j] != target[j]) { if(res[j] > 0){ i = i + (j - res[j]) ; // 原序列移动与相同前缀后缀的字符串元素个数相关 }else{ i++; // 没有相同前缀后缀字符串，自动加1 } j = res[j]; // 目标序列比较开始的位置也要变化。 }else { j++; } } if(j == len_target){ return i; } return -1; } };