diff --git a/src/regexp_nfa.c b/src/regexp_nfa.c
index 2ef13a8..df5be11 100644
--- a/src/regexp_nfa.c
+++ b/src/regexp_nfa.c
@@ -165,9 +165,9 @@
 static int *post_end;
 static int *post_ptr;
 
-static int nstate;	/* Number of states in the NFA. */
+static int nstate;	/* Number of states in the NFA. Also used when
+			 * executing. */
 static int istate;	/* Index in the state vector, used in new_state() */
-static int nstate_max;	/* Upper bound of estimated number of states. */
 
 
 static int nfa_regcomp_start __ARGS((char_u*expr, int re_flags));
@@ -219,10 +219,11 @@
     int		re_flags;	    /* see vim_regcomp() */
 {
     size_t	postfix_size;
+    int		nstate_max;
 
     nstate = 0;
     istate = 0;
-    /* A reasonable estimation for size */
+    /* A reasonable estimation for maximum size */
     nstate_max = (int)(STRLEN(expr) + 1) * NFA_POSTFIX_MULTIPLIER;
 
     /* Some items blow up in size, such as [A-z].  Add more space for that.
@@ -1968,10 +1969,20 @@
  * Frag_T.out is a list of places that need to be set to the
  * next state for this fragment.
  */
+
+/* Since the out pointers in the list are always
+ * uninitialized, we use the pointers themselves
+ * as storage for the Ptrlists. */
 typedef union Ptrlist Ptrlist;
+union Ptrlist
+{
+    Ptrlist	*next;
+    nfa_state_T	*s;
+};
+
 struct Frag
 {
-    nfa_state_T   *start;
+    nfa_state_T *start;
     Ptrlist	*out;
 };
 typedef struct Frag Frag_T;
@@ -1999,17 +2010,6 @@
 }
 
 /*
- * Since the out pointers in the list are always
- * uninitialized, we use the pointers themselves
- * as storage for the Ptrlists.
- */
-union Ptrlist
-{
-    Ptrlist	*next;
-    nfa_state_T	*s;
-};
-
-/*
  * Create singleton list containing just outp.
  */
     static Ptrlist *
@@ -3358,8 +3358,8 @@
 #endif
 
 	    case NFA_NEWL:
-		if (!reg_line_lbr && REG_MULTI
-				     && curc == NUL && reglnum <= reg_maxline)
+		if (curc == NUL && !reg_line_lbr && REG_MULTI
+						    && reglnum <= reg_maxline)
 		{
 		    go_to_nextline = TRUE;
 		    /* Pass -1 for the offset, which means taking the position
@@ -3367,6 +3367,12 @@
 		    addstate(nextlist, t->state->out, &t->sub, -1,
 							  listid + 1, &match);
 		}
+		else if (curc == '\n' && reg_line_lbr)
+		{
+		    /* match \n as if it is an ordinary character */
+		    addstate(nextlist, t->state->out, &t->sub, 1,
+							  listid + 1, &match);
+		}
 		break;
 
 	    case NFA_CLASS_ALNUM:
@@ -3832,7 +3838,12 @@
      * (and count its size). */
     postfix = re2post();
     if (postfix == NULL)
+    {
+	/* TODO: only give this error for debugging? */
+	if (post_ptr >= post_end)
+	    EMSGN("Internal error: estimated max number of states insufficient: %ld", post_end - post_start);
 	goto fail;	    /* Cascaded (syntax?) error */
+    }
 
     /*
      * In order to build the NFA, we parse the input regexp twice:
diff --git a/src/testdir/test64.in b/src/testdir/test64.in
index 1ad33d9..8d0f535 100644
--- a/src/testdir/test64.in
+++ b/src/testdir/test64.in
@@ -250,6 +250,9 @@
 :call add(tl, [2, 'abc[0-9]*ddd', 'adf abc44482ddd oijs', 'abc44482ddd'])
 :call add(tl, [2, '\_[0-9]\+', 'asfi9888u', '9888'])
 :call add(tl, [2, '[0-9\n]\+', 'asfi9888u', '9888'])
+:call add(tl, [2, '\_[0-9]\+', "asfi\n9888u", "\n9888"])
+:call add(tl, [2, '\_f', "  \na ", "\n"])
+:call add(tl, [2, '\_f\+', "  \na ", "\na"])
 :"
 :"
 :"""" Test recognition of some character classes
diff --git a/src/testdir/test64.ok b/src/testdir/test64.ok
index 31052fb..40b02cd 100644
--- a/src/testdir/test64.ok
+++ b/src/testdir/test64.ok
@@ -576,6 +576,15 @@
 OK 0 - [0-9\n]\+
 OK 1 - [0-9\n]\+
 OK 2 - [0-9\n]\+
+OK 0 - \_[0-9]\+
+OK 1 - \_[0-9]\+
+OK 2 - \_[0-9]\+
+OK 0 - \_f
+OK 1 - \_f
+OK 2 - \_f
+OK 0 - \_f\+
+OK 1 - \_f\+
+OK 2 - \_f\+
 OK 0 - [0-9]
 OK 1 - [0-9]
 OK 2 - [0-9]
diff --git a/src/version.c b/src/version.c
index f120149..a44b1e2 100644
--- a/src/version.c
+++ b/src/version.c
@@ -729,6 +729,8 @@
 static int included_patches[] =
 {   /* Add new patch number below this line */
 /**/
+    1025,
+/**/
     1024,
 /**/
     1023,