Случайный афоризм
Писатели учатся лишь тогда, когда они одновременно учат. Они лучше всего овладевают знаниями, когда одновременно сообщают их другим. Бертольт Брехт
 
новости
поиск по автору
поиск по тематике
поиск по ключевому слову
проба пера
энциклопедия авторов
словарь терминов
программы
начинающим авторам
ваша помощь
о проекте
Книжный магазин
Главная витрина
Книги компьютерные
Книги по психологии
Книги серии "Для чайников"
Книги по лингвистике
ЧАВо
Разные Статьи
Статьи по литературе

Форма пользователя
Логин:
Пароль:
регистрация
 детектив



 драмма



 животные



 история



 компьютерная документация



 медицина



 научно-популярная



 очередная история



 очерк



 повесть



 политика



 поэзия и лирика



 приключения



 психология



 религия



 студенту



 технические руководства



 фантастика



 философия и мистика



 художественная литература



 энциклопедии, словари



 эротика, любовные романы



в избранноеконтакты

Параметры текста
Шрифт:
Размер шрифта: Высота строки:
Цвет шрифта:
Цвет фона:

          3 (aba)          b             4 (abab)
          3 (aba)          a             1 (a)
          3 (aba)        кроме a,b       0
          4 (abab)         c             5 (ababc)
          4 (abab)         a             3 (aba)
          4 (abab)       кроме a,c       0

Для проверки посмотрим, к примеру, на вторую снизу строку.  Если
прочитанная  часть  кончалась на "abab", а затем появилась буква
"a", то теперь  прочитанная  часть  кончается  на  "ababa".  На-
ибольшее  начало  образца ("ababc"), которое есть ее конец - это
"aba".

     Философский вопрос: мы говорили, что  трудность  состоит  в
том,  что  есть несколько возможных положений образца, каждое из
которых может оказаться истинным. Им соответствуют несколько на-
чал образца, являющихся концами входного слова. Но конечный  ав-
томат помнит лишь самое длинное из них. Как же остальные?

     Философский ответ. Дело в том, что самое длинное из них оп-
ределяет  все остальные - это его концы, одновременно являющиеся
его началами.

     Не составляет труда для любого конкретного образца написать
программу,  осуществляющую  поиск этого образца описанным спосо-
бом.  Однако хотелось бы написать программу, которая ищет произ-
вольный образец в произвольном слове. Это  можно  делать  в  два
этапа:  сначала  по образцу строится таблица переходов конечного
автомата, а затем читается входное слово и состояние  преобразу-
ется  в  соответствии  с этой таблицей. Подобный метод часто ис-
пользуется для более сложных задач поиска (см.  далее),  но  для
поиска подслова существует более простой и эффективный алгоритм,
называемый  алгоритмом  Кнута  - Морриса - Пратта. Но прежде нам
понадобятся некоторые вспомогательные утверждения.

     10.3. Вспомогательные утверждения

     Для произвольного слова X рассмотрим все его начала, однов-
ременно  являющиеся его концами, и выберем из них самое длинное.
(Не считая, конечно, самого слова X.) Будем обозначать его n(X).

     Примеры: n(aba)=a, n(abab)=ab, n(ababa)=aba, n(abc) =  пус-
тое слово.

     10.3.1. Доказать, что все слова n(X), n(n(X)), n(n(n(X)))
и т.д. являются началами слова X.

     Решение.  Каждое из них (согласно определению) является на-
чалом предыдущего.

     По той же причине все они являются концами слова X.

     10.3.2. Доказать, что последовательность предыдущей  задачи
обрывается (на пустом слове).

     Решение. Каждое слово короче предыдущего.

     Задача.  Доказать, что любое слово, одновременно являющееся
началом и концом слова X (кроме самого X)  входит  в  последова-
тельность n(X), n(n(X)),...

1 : 2 : 3 : 4 : 5 : 6 : 7 : 8 : 9 : 10 : 11 : 12 : 13 : 14 : 15 : 16 : 17 : 18 : 19 : 20 : 21 : 22 : 23 : 24 : 25 : 26 : 27 : 28 : 29 : 30 : 31 : 32 : 33 : 34 : 35 : 36 : 37 : 38 : 39 : 40 : 41 : 42 : 43 : 44 : 45 : 46 : 47 : 48 : 49 : 50 : 51 : 52 : 53 : 54 : 55 : 56 : 57 : 58 : 59 : 60 : 61 : 62 : 63 : 64 : 65 : 66 : 67 : 68 : 69 : 70 : 71 : 72 : 73 : 74 : 75 : 76 : 77 : 78 : 79 : 80 : 81 : 82 : 83 : 84 : 85 : 86 : 87 : 88 : 89 : 90 : 91 : 92 : 93 : 94 : 95 : 96 : 97 : 98 : 99 : 100 : 101 : 102 : 103 : 104 : 105 : 106 : 107 : 108 : 109 : 110 : 111 : 112 : 113 : 114 : 115 : 116 : 117 : 118 : 119 : 120 : 121 : 122 : 123 : 124 : 125 : 126 : 127 : 128 : 129 : 130 : 131 : 132 : 133 : 134 : 135 : 136 : 137 : 138 : 139 : 140 : 141 : 142 : 143 : 144 : 145 : 146 : 147 : 148 : 149 : 150 : 151 : 152 : 153 : 154 : 155 : 156 : 157 : 158 : 159 : 160 : 161 : 162 : 163 : 164 : 165 : 166 : 167 : 168 : 169 : 170 : 171 : 172 : 173 : 174 : 175 : 176 : 177 : 178 : 179 : 180 : 181 : 182 : 183 : 184 : 185 : 186 : 187 : 188 : 189 : 190 : 191 : 192 : 193 : 194 : 195 : 196 : 197 : 198 : 199 : 200 : 201 : 202 : 203 : 204 : 205 : 206 : 207 : 208 : 209 : 210 : 211 : 212 : 213 : 214 : 215 : 216 : 217 : 218 : 219 : 220 : 221 : 222 : 223 : 224 : 225 : 226 : 227 : 228 : 229 : 230 : 231 : 232 : 233 : 234 : 235 : 236 : 237 : 238 : 239 : 240 : 241 : 242 : 243 : 244 : 245 : 246 : 247 : 248 : 249 : 250 : 251 : 252 : 253 : 254 : 255 : 256 : 257 : 258 : 259 : 260 : 261 : 262 : 263 : 264 : 265 : 266 : 267 : 268 : 269 : 270 : 271 : 272 : 273 : 274 : 275 : 276 : 277 : 278 : 279 : 280 : 281 : 282 : 283 : 284 : 285 : 286 : 287 : 288 : 289 : 290 : 291 : 292 : 293 : 294 : 295 : 296 : 297 : 298 : 299 : 300 : 301 : 302 : 303 : 304 : 305 : 306 : 307 : 308 : 309 : 310 : 311 : 312 : 313 : 314 : 315 : 316 : 317 : 318 : 319 : 320 : 321 : 322 : 323 : 324 : 325 : 326 : 327 : 328 : 329 : 330 : 331 : 332 : 333 : 334 : 335 : 336 : 337 : 338 : 339 : 340 : 341 : 342 : 343 : 344 : 345 : 346 : 347 : 348 : 349 : 350 : 351 : 352 : 353 : 354 : 355 : 356 : 357 : 358 : 359 : 360 : 361 : 362 : 363 : 364 : 365 : 366 : 367 : 368 : 369 : 370 : 371 : 372 : 373 : 374 : 375 : 376 : 377 : 378 : 379 : 380 : 381 : 382 : 383 : 384 : 385 : 386 : 387 : 388 : 389 : 390 : 391 : 392 : 393 : 394 : 395 : 396 : 397 : 398 : 399 : 400 : 401 : 402 : 403 : 404 : 405 : 406 : 407 : 408 : 409 : 410 : 411 : 412 : 413 : 414 : 415 : 416 : 417 : 418 : 419 : 420 : 421 : 422 : 423 : 424 : 425 :
главная наверх

(c) 2008 Большая Одесская Библиотека.