"When implementing a search engine, I would like you to digest the results of ""Tokyo"" from the inputs ""Tou,"" ""tok,"" and ""East."""

How can I accomplish the following?
I have also discussed my own ideas on how to realize it later, so I would appreciate it if you could refer to them as well.
Thank you for your cooperation.

Pass a string by API parameters.I want to use that as a key to search from the text list.
Specifically,
for inputs such as "to", "tok", and "east". We would like to obtain the result "Tokyo" from the list of prefectures described below.
It's OK that sugar gets stuck when you say "to"

Tokyo Kyoto
Hokkaido Fukuoka
Sugar content

文章 It's okay to assume that it's already parsed to the word level, not to the sentence
※ Hundreds of records at most (performance is a concern)

Rails 4.2.6
AWS EC2+ RDS for MYSQL 5.7

Search like in MySQL normally
"If you don't type ""East"", it won't get stuck
" If you prepare columns in hiragana and alphabets and search like them,
Can I use hiragana or alphabet?
※ There are not many records, so I don't care about the speed.
※ I think I can use kakasi

Full-text index in MySQL 5.7 Similar to 1, you have to create transposition indexes for hiragana, alphabet, and kanji.
※ For your information, only N-gram parsers are available on RDS.

Elastic search
It seems difficult to put it in (I haven't tried it).I would like to implement it at no cost this time
If you add Kuromoji, you can link kanji to reading.

If there's anything else,

Other

If you search Google, Tokyo will be digested even if you add "Tokyo ky", but
I wonder how they implement it...