Алгоритм Кнута-Морриса-Пратта (КМП) получает на  вход слово   X=x[1]x[2]... x[n]  и просматривает его слева направо буква за буквой, заполняя при этом массив натуральных чисел l[1]... l[n], где   l[i]=длина слова l(x[1]...х[i])  (функция l определена в предыдущем пункте). Словами: l[i] есть длина наибольшего начала слова x[1]...x[i], одновременно являющегося его концом.

Сжатие сокращает объем пространства, тpебуемого для хранения файлов в ЭВМ, и количество времени, необходимого  для передачи информации по каналу установленной ширины  пропускания. Это есть форма кодирования.

Фундаментальной  чертой  цивилизации является рост производства,  потребления и накопления  информации во все отраслях  человеческой деятельности.  Вся жизнь человека  так или  иначе связана  с  получением,  накоплением  и обработкой информации.