Vi anser att problemet med att utveckla algoritmer för igenkänning av ett fast mönster inom en permutation. Dessa metoder är baserade på att använda en noggrant utvald kedja eller träd subpatterns för att bygga upp hela mönstret. I allmänhet kan man uppnå stora förbättringar när det gäller brute force-sökning. Även med hjälp av online-versioner av dessa metoder ger sådana förbättringar, även om dessa ofta inte är lika bra som för den fullständiga metoden. Dessutom, genom att använda noggrant utvalda datastrukturer för att finjustera metoderna, fastställer vi att alla mönster av längd 4 kan detekteras i O(n log n) tid. Vi förbättrar också komplexiteten bundet för detektion av ett separat mönster från O(n 6 ) till O(n 5 log n).
-För alla mönster av längd fyra PPM kan lösas i O (n log n)-tid REF.
Algorithms for pattern involvement in permutations
{'venue': 'in Algorithms and Computation, 12th International Symposium, ISAAC 2001, Proceedings LNCS 2223', 'journal': None, 'mag_field_of_study': ['Computer Science']}