a***e
发帖数: 413 | 1 请问这段程序有问题么？能通过OJ。但总觉得似乎太简洁了。。。。。有人被面试的时
候要求当场写KMP么？多谢！
char *strstr(const char *s1, const char *s2) {
const char *a = s1, *b = s2;
while(1)
{
if (!*b) return (char *)s1;
else if (!*a) return NULL;
else if (*a++ != *b++) {a = ++s1; b = s2;}
}
} |
d**********u
发帖数: 3371 | 2 KMP也也不难吧. 能过OJ不代表什么
【在 a***e 的大作中提到】
: 请问这段程序有问题么？能通过OJ。但总觉得似乎太简洁了。。。。。有人被面试的时
: 候要求当场写KMP么？多谢！
: char *strstr(const char *s1, const char *s2) {
: const char *a = s1, *b = s2;
: while(1)
: {
: if (!*b) return (char *)s1;
: else if (!*a) return NULL;
: else if (*a++ != *b++) {a = ++s1; b = s2;}
: }
|
a***e
发帖数: 413 | |
c*******y
发帖数: 98 | 4 求KMP讲解链接，我看过一个帖子，理解了为什么要做那样的index，但看不懂index怎
么做的，为什么可以O(n)做出来。
【在 d**********u 的大作中提到】
: KMP也也不难吧. 能过OJ不代表什么
|
Z**********4
发帖数: 528 | 5 这个可以过oj啊。。
我记得这种naive matching不能过的。 |
a***e
发帖数: 413 | 6 http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt
不知道啊，但好像是可以得。我是觉得这种写法很简单， 比起同样的naive matching
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;
const char *p1_advance = haystack;
for (p2 = &needle[1]; *p2; ++p2) {
p1_advance++; // advance p1_advance M-1 times
}
for (p1 = haystack; *p1_advance; p1_advance++) {
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
} |
a***e
发帖数: 413 | 7 找到一个解释比wiki清楚的source
http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.h
下面是根据那个原理写的KMP，这下觉得清楚多了。和正在学习的同学共享一下。。。
。。。顺便多谢各位。。。。
class Solution {
public:
char *strStr(char *haystack, char *needle) {
int pos = kmpSearch(haystack, needle);
if (pos == -1) return nullptr;
else return haystack + pos;
}
static void kmpPreprocess(const char *p, vector &b)
{
int i = 0, j = -1;
b[i] = j;
const int m = strlen(p);
while (i
{
while (j >= 0 && p[i] != p[j]) j = b[j];
i++; j++;
b[i] = j;
}
}
static int kmpSearch(const char *t, const char *p)
{
int i = 0, j = 0;
int n = strlen(t);
int m = strlen(p);
if (m==0) return 0;
// int *b = new int[m+1];
vector b(m+1,0);
kmpPreprocess(p, b);
while (i
{
while (j >= 0 && t[i] != p[j]) j = b[j];
i++; j++;
if (j == m)
{
//delete[]b;
return (i - j);
}
}
return -1;
}
}; |
