Перед отъездом со своими дочерями на королевский бал злая мачеха приказала к утру Золушке отделить «хорошие» гиперссылки от «плохих» внутри файла links.txt (каждая гиперссылка содержится в отдельной строке этого файла). Чтобы отличить «хорошие»гиперссылки от «плохих»мачеха дала ей текстовый файл rules.txtс правилами, описывающими плохие гиперссылки. Каждое правило находится в отдельной строке и может принимать одну из двух форм:
– http://www.nsa.*, где * ноль и более символов;
– *.nsa.gov, где * ноль и более символов.
К утру мачеха ждет от Золушки файлbad_links.txt с выделенными «плохими»гиперссылками из файла links.txt. Напишите программу, которая поможет Золушке выделить «плохие» гиперссылки и попасть на бал при условии, что он начнется через 5 секунд.
Пусть в файле links.txt содержится M записей, а в файле rules.txt содержится N записей. Прямая проверка каждой гиперссылки с каждым правилом дает алгоритм сложности O(N*M), что не позволяет уложиться в ограничение 5 секунд при заданных файлах links.txtи rules.txt.
Для ускорения проверки каждой гиперссылки предлагается выполнить предварительную обработку файла rules.txtразделив все правила на два множества: заканчивающиеся на «*» и начинающиеся c«*».
Из всех правил, заканчивающихся «*» производится удаление конечной «*» и перевод результата к нижнему регистру. Полученные таким образом правила сортируются в лексикографическом порядке.
Из всех правила, начинающихся со «*» производится удаление начальной «*», перевести к нижнему регистру и записать в обратном порядке. Полученные таким образом правила сортируются в лексикографическом порядке.
Теперь для проверки того является ли очередная гиперссылка из файла links.txt «плохой» достаточно привести ее к нижнему регистру и проверить с помощью алгоритма бинарного поиска ее наличие в первом множестве (при этом критерием равенство будет то, что гиперссылка начинается с преобразованного правила). Если гиперссылка не была найдена в первом множестве, то она записывается в обратном порядке, приводится к нижнему регистру и ищется аналогично предыдущему случаю во втором множестве. Если гиперссылка не была найдена ни в первом и ни во втором множестве, то она является «хорошей».
Пусть в файле links.txt содержится M записей, а в файле rules.txt содержитсяN записей. Прямая проверка каждой гиперссылки с каждым правилом дает алгоритм сложности O(N*M), что не позволяет уложиться в ограничение 5 секунд при заданных файлах links.txtи rules.txt.
Для ускорения проверки каждой гиперссылки предлагается выполнить предварительную обработку файла rules.txtразделив все правила на два множества: заканчивающиеся на «*» и начинающиеся c«*».
Из всех правил, заканчивающихся «*» производится удаление конечной «*» и перевод результата к нижнему регистру. Полученные таким образом правила сортируются в лексикографическом порядке.
Из всех правила, начинающихся со «*» производится удаление начальной «*», перевести к нижнему регистру и записать в обратном порядке. Полученные таким образом правила сортируются в лексикографическом порядке.
Теперь для проверки того является ли очередная гиперссылка из файлаlinks.txt «плохой» достаточно привести ее к нижнему регистру и проверить с помощью алгоритма бинарного поиска ее наличие в первом множестве (при этом критерием равенство будет то, что гиперссылка начинается с преобразованного правила). Если гиперссылка не была найдена в первом множестве, то она записывается в обратном порядке, приводится к нижнему регистру и ищется аналогично предыдущему случаю во втором множестве. Если гиперссылка не была найдена ни в первом и ни во втором множестве, то она является «хорошей».