Search API does not do this; see Partial matching GAE search API and GAE Full Text Search: can only match exact word? how to search like contains(...)? for similar discussions.
At my company we have implemented the mentioned tokenization approach and it seems to work reasonably well. One approach for your problem would be to normalize to ASCII when you're doing the tokenization. See What is the best way to remove accents in a Python unicode string? for some how-tos on that.