Search Auto-Complete for Special Languages

Problem statement

Some languages, like Persian, are written from right to left instead of left to right. We have to design an auto-complete feature for such languages. We're provided with a list of keywords and a query string. Design a system that provides query suggestions from the keyword list to the user every time the user types a character of the query string.

Example

Sample input