diff --git a/Objects/stringobject.c b/Objects/stringobject.c
index 9f41317..0b79a06 100644
--- a/Objects/stringobject.c
+++ b/Objects/stringobject.c
@@ -2215,11 +2215,11 @@
 	char *new_s;
 	int nfound, offset, new_len;
 
-	if (len == 0 || pat_len > len)
+	if (len == 0 || (pat_len == 0 && sub_len == 0) || pat_len > len)
 		goto return_same;
 
 	/* find length of output string */
-	nfound = mymemcnt(str, len, pat, pat_len);
+	nfound = (pat_len > 0) ? mymemcnt(str, len, pat, pat_len) : len + 1;
 	if (count < 0)
 		count = INT_MAX;
 	else if (nfound > count)
@@ -2242,25 +2242,38 @@
 			return NULL;
 		out_s = new_s;
 
-		for (; count > 0 && len > 0; --count) {
-			/* find index of next instance of pattern */
-			offset = mymemfind(str, len, pat, pat_len);
-			if (offset == -1)
-				break;
+		if (pat_len > 0) {
+			for (; nfound > 0; --nfound) {
+				/* find index of next instance of pattern */
+				offset = mymemfind(str, len, pat, pat_len);
+				if (offset == -1)
+					break;
 
-			/* copy non matching part of input string */
-			memcpy(new_s, str, offset);
-			str += offset + pat_len;
-			len -= offset + pat_len;
+				/* copy non matching part of input string */
+				memcpy(new_s, str, offset);
+				str += offset + pat_len;
+				len -= offset + pat_len;
 
-			/* copy substitute into the output string */
-			new_s += offset;
-			memcpy(new_s, sub, sub_len);
-			new_s += sub_len;
+				/* copy substitute into the output string */
+				new_s += offset;
+				memcpy(new_s, sub, sub_len);
+				new_s += sub_len;
+			}
+			/* copy any remaining values into output string */
+			if (len > 0)
+				memcpy(new_s, str, len);
 		}
-		/* copy any remaining values into output string */
-		if (len > 0)
-			memcpy(new_s, str, len);
+		else {
+			for (;;++str, --len) {
+				memcpy(new_s, sub, sub_len);
+				new_s += sub_len;
+				if (--nfound <= 0) {
+					memcpy(new_s, str, len);
+					break;
+				}
+				*new_s++ = *str;
+			}
+		}
 	}
 	*out_len = new_len;
 	return out_s;
@@ -2317,10 +2330,6 @@
 	else if (PyObject_AsCharBuffer(replobj, &repl, &repl_len))
 		return NULL;
 
-	if (sub_len <= 0) {
-		PyErr_SetString(PyExc_ValueError, "empty pattern string");
-		return NULL;
-	}
 	new_s = mymemreplace(str,len,sub,sub_len,repl,repl_len,count,&out_len);
 	if (new_s == NULL) {
 		PyErr_NoMemory();
diff --git a/Objects/unicodeobject.c b/Objects/unicodeobject.c
index b264936..6dea94f 100644
--- a/Objects/unicodeobject.c
+++ b/Objects/unicodeobject.c
@@ -3494,11 +3494,6 @@
 {
     PyUnicodeObject *u;
 
-    if (str1->length == 0) {
-	PyErr_SetString(PyExc_ValueError, "empty pattern string");
-	return NULL;
-    }
-
     if (maxcount < 0)
 	maxcount = INT_MAX;
 
@@ -3549,19 +3544,30 @@
             if (u) {
                 i = 0;
                 p = u->str;
-                while (i <= self->length - str1->length)
-                    if (Py_UNICODE_MATCH(self, i, str1)) {
-                        /* replace string segment */
+                if (str1->length > 0) {
+                    while (i <= self->length - str1->length)
+                        if (Py_UNICODE_MATCH(self, i, str1)) {
+                            /* replace string segment */
+                            Py_UNICODE_COPY(p, str2->str, str2->length);
+                            p += str2->length;
+                            i += str1->length;
+                            if (--n <= 0) {
+                                /* copy remaining part */
+                                Py_UNICODE_COPY(p, self->str+i, self->length-i);
+                                break;
+                            }
+                        } else
+                            *p++ = self->str[i++];
+                } else {
+                    while (n > 0) {
                         Py_UNICODE_COPY(p, str2->str, str2->length);
                         p += str2->length;
-                        i += str1->length;
-                        if (--n <= 0) {
-                            /* copy remaining part */
-                            Py_UNICODE_COPY(p, self->str+i, self->length-i);
+                        if (--n <= 0)
                             break;
-                        }
-                    } else
                         *p++ = self->str[i++];
+                    }
+                    Py_UNICODE_COPY(p, self->str+i, self->length-i);
+                }
             }
         }
     }