Детерминистички коначни аутомат

Наишао сам на интересантан практичан проблем.

Уколико имам низ познатих стрингова, хоћу да конструишем ДКА који ће препознавати да ли је дати стринг дат на улазу унутар низа.

Интересује ме само најбржа могућа варијанта. За вежбу сам направио мали генератор switch исказа али то даје веома велики бинарни код, а вероватно и даље није оптималан (на пример, поређење се врши на појединачним бајтовима иако би на 32-битним процесорима 32-битно поређење било далеко брже).

Ручно, вероватно бих пришао проблему овако:

(конструкција машине - генерисање кода):
а) Одреди најмању и највећу дужину стринга из фиксног скупа
б) Сортирај и рангирај према дужини, а у поређењу са ширином регистра на циљној машини (на пример, за 32 битне, 4 бајта).

Генерисани код би реадио отприлике овако:
1) Одреди дужину улазног стринга.
2) Изврши елиминацију на основу мин. макс. дужине.
3) на основу ранга (дужине) стринга а у функцији мин. дужине, врши одговарајућу претрагу сортираног ранга (на пример: дужина улазног стринга је 5, а најмања дужина константи је 4 а највећа 10, изабери ранг константи дужине веће од 4 а мање од 9, и врши претрагу поређењем првих 4 бајта дужине):

extern const char *const ulaz;
switch (*(uint32_t*)ulaz) {
case konst1:
...
case konst2:
...
}

где су konst1 и konst2 израчунате приликом генерисања кода на основу циљне машине и ендијана.


Ипак, претпоставио бих да ово већ негде постоји, само треба наћи.