Index: uspace/lib/posix/string.c
===================================================================
--- uspace/lib/posix/string.c	(revision c53a7058118854e855fbb20ae8db4911bd30460b)
+++ uspace/lib/posix/string.c	(revision 7e10aeee595bef589e5cf5c2e172243469e0c4f6)
@@ -48,22 +48,4 @@
 
 /**
- * Decides whether s2 is a prefix of s1.
- *
- * @param s1 String in which to look for a prefix.
- * @param s2 Prefix string to look for.
- * @return True if s2 is a prefix of s1, false otherwise.
- */
-static bool begins_with(const char *s1, const char *s2)
-{
-	while (*s1 == *s2 && *s2 != '\0') {
-		s1++;
-		s2++;
-	}
-	
-	/* true if the end was reached */
-	return *s2 == '\0';
-}
-
-/**
  * The same as strpbrk, except it returns pointer to the nul terminator
  * if no occurence is found.
@@ -471,5 +453,5 @@
 
 /**
- * Find a substring.
+ * Find a substring. Uses Knuth-Morris-Pratt algorithm.
  *
  * @param s1 String in which to look for a substring.
@@ -478,22 +460,48 @@
  *     not found.
  */
-char *posix_strstr(const char *s1, const char *s2)
-{
-	assert(s1 != NULL);
-	assert(s2 != NULL);
-
-	/* special case - needle is an empty string */
-	if (*s2 == '\0') {
-		return (char *) s1;
-	}
-
-	// TODO: use faster algorithm
-	/* check for prefix from every position - quadratic complexity */
-	while (*s1 != '\0') {
-		if (begins_with(s1, s2)) {
-			return (char *) s1;
-		}
+char* posix_strstr (const char* haystack, const char* needle)
+{
+	assert(haystack != NULL);
+	assert(needle != NULL);
+	
+	/* Special case - needle is an empty string. */
+	if (needle[0] == '\0') {
+		return (char*) haystack;
+	}
+	
+	/* Preprocess needle. */
+	size_t nlen = posix_strlen(needle);
+	size_t prefix_table[nlen + 1];
+	
+	{
+		size_t i = 0;
+		ssize_t j = -1;
 		
-		s1++;
+		prefix_table[i] = j;
+		
+		while (i < nlen) {
+			while (j >= 0 && needle[i] != needle[j]) {
+				j = prefix_table[j];
+			}
+			i++; j++;
+			prefix_table[i] = j;
+		}
+	}
+	
+	/* Search needle using the precomputed table. */
+	size_t npos = 0;
+	
+	for (size_t hpos = 0; haystack[hpos] != '\0'; ++ hpos) {
+		while (npos != 0 && haystack[hpos] != needle[npos]) {
+			npos = prefix_table[npos];
+		}
+		
+		if (haystack[hpos] == needle[npos]) {
+			npos ++;
+			
+			if (npos == nlen) {
+				return (char*) (haystack + hpos - nlen + 1);
+			}
+		}
 	}
 	
Index: uspace/lib/posix/string.h
===================================================================
--- uspace/lib/posix/string.h	(revision c53a7058118854e855fbb20ae8db4911bd30460b)
+++ uspace/lib/posix/string.h	(revision 7e10aeee595bef589e5cf5c2e172243469e0c4f6)
@@ -86,5 +86,5 @@
 extern size_t posix_strcspn(const char *s1, const char *s2);
 extern size_t posix_strspn(const char *s1, const char *s2);
-extern char *posix_strstr(const char *s1, const char *s2);
+extern char *posix_strstr(const char *haystack, const char *needle);
 
 /* Collation Functions */