Fast Convolutions of Packed Strings and Pattern Matching with Wildcards

摘要: We give faster methods to compute discrete convolutions. assume that all the inputs are packed, is, strings packed into words such each word is with α = ⌊ ω / log⁡2|Σ| ⌋ characters, where w length of a machine and ∑ alphabet. The output our also contains more than one element result. approach based on word-level parallelism FFT. Given two m n ( ≥ ) characters ⌈ m/α ⌉ n/α respectively, convolution them can be computed in O(nuw log⁡ muw) time, u (⌈ log⁡|Σ|m + 2) by Experiments show method three times using standard trick. consider problem pattern matching wildcards strings. It finds occurrences text, both which may contain wildcards. By strings, we present algorithms previous O(n m)-time algorithm, text. algorithm runs muw nlog⁡ |Σ|w log⁡1+o(1) |Σ| mlog⁡ wlog⁡ occ) occ number input. bit-parallel wildcard for long patterns.