2014
11-18

# LeetCode-Implement strStr()[字符串]

### Implement strStr()

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Update (2014-11-02):
The signature of the function had been updated to return the index instead of the pointer. If you still see your function signature returns a char * or String, please click the reload button to reset your code definition.

// LeetCode, Implement strStr()
// 暴力解法，时间复杂度O(N*M)，空间复杂度O(1)
class Solution {
public:
char *strStr(const char *haystack, const char *needle) {
// if needle is empty return the full string
if (!*needle) return (char*) haystack;

const char *p1;
const char *p2;
for (p2 = &needle[1]; *p2; ++p2) {
}

char *p1_old = (char*) p1;
p2 = needle;
while (*p1 && *p2 && *p1 == *p2) {
p1++;
p2++;
}
if (!*p2) return p1_old;

p1 = p1_old + 1;
}
return nullptr;
}
};


// LeetCode, Implement strStr()
// KMP，时间复杂度O(N+M)，空间复杂度O(M)
class Solution {
public:
char *strStr(const char *haystack, const char *needle) {
int pos = kmp(haystack, needle);
if (pos == -1) return nullptr;
else return (char*)haystack + pos;
}
private:
/*
* @brief 计算部分匹配表，即next数组.
*
* @param[in] pattern 模式串
* @param[out] next next数组
* @return 无
*/
static void compute_prefix(const char *pattern, int next[]) {
int i;
int j = -1;
const int m = strlen(pattern);

next[0] = j;
for (i = 1; i < m; i++) {
while (j > -1 && pattern[j + 1] != pattern[i]) j = next[j];

if (pattern[i] == pattern[j + 1]) j++;
next[i] = j;
}
}

/*
* @brief KMP算法.
*
* @param[in] text 文本
* @param[in] pattern 模式串
* @return 成功则返回第一次匹配的位置，失败则返回-1
*/
static int kmp(const char *text, const char *pattern) {
int i;
int j = -1;
const int n = strlen(text);
const int m = strlen(pattern);
if (n == 0 && m == 0) return 0; /* "","" */
if (m == 0) return 0;  /* "a","" */
int *next = (int*)malloc(sizeof(int) * m);

compute_prefix(pattern, next);

for (i = 0; i < n; i++) {
while (j > -1 && pattern[j + 1] != text[i]) j = next[j];

if (text[i] == pattern[j + 1]) j++;
if (j == m - 1) {
free(next);
return i-j;
}
}

free(next);
return -1;
}
};


1. 在鼬回忆里止水给团藏拿走一直眼睛后给追杀，在躲不开团藏手下法术的时候开启须佐挡住攻击，这个时候鼬救走止水后就在瀑布哪里把最后一直眼睛交给鼬保管，后自杀。

2. 在鼬回忆里止水给团藏拿走一直眼睛后给追杀，在躲不开团藏手下法术的时候开启须佐挡住攻击，这个时候鼬救走止水后就在瀑布哪里把最后一直眼睛交给鼬保管，后自杀。

3. 在鼬回忆里止水给团藏拿走一直眼睛后给追杀，在躲不开团藏手下法术的时候开启须佐挡住攻击，这个时候鼬救走止水后就在瀑布哪里把最后一直眼睛交给鼬保管，后自杀。

4. 在鼬回忆里止水给团藏拿走一直眼睛后给追杀，在躲不开团藏手下法术的时候开启须佐挡住攻击，这个时候鼬救走止水后就在瀑布哪里把最后一直眼睛交给鼬保管，后自杀。

5. 在鼬回忆里止水给团藏拿走一直眼睛后给追杀，在躲不开团藏手下法术的时候开启须佐挡住攻击，这个时候鼬救走止水后就在瀑布哪里把最后一直眼睛交给鼬保管，后自杀。

6. 在鼬回忆里止水给团藏拿走一直眼睛后给追杀，在躲不开团藏手下法术的时候开启须佐挡住攻击，这个时候鼬救走止水后就在瀑布哪里把最后一直眼睛交给鼬保管，后自杀。

7. 在鼬回忆里止水给团藏拿走一直眼睛后给追杀，在躲不开团藏手下法术的时候开启须佐挡住攻击，这个时候鼬救走止水后就在瀑布哪里把最后一直眼睛交给鼬保管，后自杀。

8. 在鼬回忆里止水给团藏拿走一直眼睛后给追杀，在躲不开团藏手下法术的时候开启须佐挡住攻击，这个时候鼬救走止水后就在瀑布哪里把最后一直眼睛交给鼬保管，后自杀。

9. Gucci New Fall Arrivals

This is really nice to know. I hope it will be successful in the future. Good job on this and keep up the good work.

10. #include <cstdio>
#include <cstring>

const int MAXSIZE=256;
//char store[MAXSIZE];
char str1[MAXSIZE];
/*
void init(char *store) {
int i;
store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
for(i=’F';i<=’Z';++i) store =i-5;
}
*/
int main() {
//freopen("input.txt","r",stdin);
//init(store);
char *p;
while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
if(p=fgets(str1,MAXSIZE,stdin)) {
for(;*p;++p) {
//*p=store[*p]
if(*p<’A’ || *p>’Z') continue;
if(*p>’E') *p=*p-5;
else *p=*p+21;
}
printf("%s",str1);
}
fgets(str1,MAXSIZE,stdin);
}
return 0;
}