http://oj.leetcode.com/problems/implement-strstr/
判断一个串是否为另一个串的子串
比较简单的方法，复杂度为O(m*n),另外还可以用KMP时间复杂度为O(m+n)，之前面试的时候遇到过。
class Solution {
public:
bool isEqual(char *a,char *b)
{
char* chPointer = a;
char* chPointer2 = b;
while(*chPointer2!= '\0' && *chPointer!='\0' )
{
if(*chPointer == *chPointer2)
{
chPointer++;
chPointer2++;
}
else
return false;
}
return true;
}
char *strStr(char *haystack, char *needle) {
char* chPointer = haystack;
char* chPointer2 = needle;
if(haystack == NULL || needle ==NULL || haystack =="")
return NULL;
while(chPointer)
{
if(isEqual(chPointer,needle))
return chPointer;
chPointer++;
}
return NULL;
}
};class Solution {
public:
void compute_prefix(const char* pattern,int next[])
{
int i;
int j = -;
const int m = strlen(pattern);
next[] = j;
for(i =;i<m;i++)
{
while(j>- && pattern[j+] != pattern[i]) j = next[j];
if(pattern[i]== pattern[j+])
j++;
next[i] = j;
}
}
int kmp(const char* text , const char* pattern)
{
int i;
int j = -;
const int n = strlen(text);
const int m = strlen(pattern);
if(n == m && m==)
return ;
if(m == )
return ;
int *next = (int *)malloc(sizeof(int) * m);
compute_prefix(pattern, next);
for(i = ;i <n;i++)
{
while(j >- && pattern[j+] != text[i])
j = next[j];
if(text[i] == pattern[j+]) j++;
if(j==m-)
{
free(next);
return i-j;
}
}
}
char *strStr(char *haystack, char *needle) {
int position = kmp(haystack,needle);
if(position == -)
return NULL;
else
return (char*)haystack + position;
}
};