finding a+rev(a) +.* is as good as finding --> a+rev(a) The pattern searching is usuaally done in O(n) time if I'm not mistaken.
find the info below.. DID YOU ASK something else? Single pattern algorithms Let *m* be the length of the pattern and let *n* be the length of the searchable text. Algorithm Preprocessing time Matching time1 Naïve string search algorithm 0 (no preprocessing) Θ((n-m+1) m) Rabin–Karp string search algorithm<http://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_string_search_algorithm> Θ(m) average Θ(n+m), worst Θ((n-m+1) m) Finite-state automaton<http://en.wikipedia.org/wiki/Finite-state_machine>based search Θ(m |Σ|) Θ(n) Knuth–Morris–Pratt algorithm<http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm> Θ(m) Θ(n) Boyer–Moore string search algorithm<http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm> Θ(m + |Σ|) Ω(n/m), O(n) Bitap algorithm<http://en.wikipedia.org/wiki/Bitap_algorithm>( *shift-or*, *shift-and*, *Baeza–Yates–Gonnet*) Θ(m + |Σ|) O(mn) SOURCE: http://en.wikipedia.org/wiki/String_searching_algorithm -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
