Fast and flexible packed string matching

摘要: Searching for all occurrences of a pattern in text is fundamental problem computer science with applications many other fields, like natural language processing, information retrieval and computational biology. In the last two decades general trend has appeared trying to exploit power word RAM model speed-up performances classical string matching algorithms. this an algorithm operates on words length w, grouping blocks characters, arithmetic logic operations take one unit time.In paper we use specialized word-size packed instructions, based Intel streaming SIMD extensions (SSE) technology, design very fast algorithm. We evaluate our solution terms efficiency, stability flexibility, where propose deviation running time distinct equal patterns as measure stability.From experimental results it turns out that, despite their quadratic worst case complexity, new presented becomes clear winner average cases, when compared against most recent effective algorithms known literature. A instructions.The works using technology.We prove effectiveness times, flexibility.Our be fastest short case.We conduct discuss wide series tests.