Hey Miguel!
There are currently two search engines implemented. The one you use when you start typing in the search box in the upper right corner is currently based on a MySQL prefix search. We are actually working on changing this, but this will take time.
When you are using Special:Search you are using an other search algorithm that, I believe, supports what you want. You can try this on wikidata.org: Typing "Comite" in the upper right will not find "Comité", but Special:Search will.
You may need to install https://www.mediawiki.org/wiki/Extension:CirrusSearch to have this feature in your installation.
Best Thiemo