Аннотация:
Рассматривается так называемое LZ-разложение данного слова в конечном алфавите. LZ-разложение данного слова $W$ — это представление $W$ в виде произведения слов $X_1 X_2\dots X_n$, определяемого индукцией. $X_1$ — это первая буква слова $W$. Пусть $X_1 X_2\dots X_i$ есть разложение начала $W_1$ слова $W = W_1 W_2$. Если первая буква слова $W_2$ не встречалась в $W_1$, то она берется в качестве $X_{i+1}$. В противном случае, в качестве $X_{i+1}$ берется максимальное по длине начало слова $W_2$, для которого есть вхождение в слово $W$, пересекающееся c $W_1$. В докладе будет предложен новый алгоритм вычисления LZ-разложения данного слова на РАМ-машине и даны оценки на емкостную и временную сложности его работы.
|
