<?php
 
$input = 'к';
 
$data = array('Москва', 'Балашиха', 'Химки', 'Подольск', 'Королев', 'Электросталь', 'Коломна');
 
$input = mb_strtolower($input);
$result = array_filter($data, function ($item) use ($input) {
	if (mb_stripos(mb_strtolower($item), $input) === 0) {
		return true;
	}
	return false;
});
 
echo '<ul>';
echo '<li>' . implode( '</li><li>', $result) . '</li>';
echo '</ul>';

PD9waHAKCiRpbnB1dCA9ICfQuic7CgokZGF0YSA9IGFycmF5KCfQnNC+0YHQutCy0LAnLCAn0JHQsNC70LDRiNC40YXQsCcsICfQpdC40LzQutC4JywgJ9Cf0L7QtNC+0LvRjNGB0LonLCAn0JrQvtGA0L7Qu9C10LInLCAn0K3Qu9C10LrRgtGA0L7RgdGC0LDQu9GMJywgJ9Ca0L7Qu9C+0LzQvdCwJyk7CgokaW5wdXQgPSBtYl9zdHJ0b2xvd2VyKCRpbnB1dCk7CiRyZXN1bHQgPSBhcnJheV9maWx0ZXIoJGRhdGEsIGZ1bmN0aW9uICgkaXRlbSkgdXNlICgkaW5wdXQpIHsKCWlmIChtYl9zdHJpcG9zKG1iX3N0cnRvbG93ZXIoJGl0ZW0pLCAkaW5wdXQpID09PSAwKSB7CgkJcmV0dXJuIHRydWU7Cgl9CglyZXR1cm4gZmFsc2U7Cn0pOwoKZWNobyAnPHVsPic7CmVjaG8gJzxsaT4nIC4gaW1wbG9kZSggJzwvbGk+PGxpPicsICRyZXN1bHQpIC4gJzwvbGk+JzsKZWNobyAnPC91bD4nOw==