NFA state complexity for the complement of EPAL restricted to a fixed length I've been having trouble proving the next statement:


  Let $L_n=\{ww, |w|=n\}$ (the set of equal-length palindromes (EPAL) restricted to length $2n$). Prove that $L^c_n$ can be accepted by an NFA with at most $O(n^2)$ states.


What I've been trying to do is that the complement of $L_n$ is 

$\qquad\displaystyle L^c_n = \{w , |w| \not = 2n\} \cup \{ww', w \not = w'\}$. 

I want a hint on what to think to prove this thanks!
Hint: further break up the difficult case $\{ww' : |w|=|w'|=n,w\neq w'\}$ as a sum $$\bigcup_{i=1}^n \{ \Sigma^{i-1} \alpha \Sigma^{n-i} \Sigma^{i-1} \alpha' \Sigma^{n-i} : \alpha \neq \alpha' \in \Sigma \}. $$
In total there are $n+1$ cases (including $\{w : |w| \neq 2n\}$), so if you can implement each one in $O(n)$ states, you're done.