• DocumentCode
    3523636
  • Title

    A fast string matching algorithm based on lowlight characters in the pattern

  • Author

    Zhengjun Cao ; Zhenzhen Yan ; Lihua Liu

  • Author_Institution
    Dept. of Math., Shanghai Univ., Shanghai, China
  • fYear
    2015
  • fDate
    27-29 March 2015
  • Firstpage
    179
  • Lastpage
    182
  • Abstract
    String matching is of great importance in pattern recognition. We put forth a new string matching algorithm which matches the pattern from neither the left nor the right end, instead a special position. Comparing with the Knuth-Morris-Pratt algorithm and the Boyer-Moore algorithm, the new algorithm is more flexible to pick the position for starting comparisons. The option really brings it a saving in cost. The method requires a statistical probability table for alphabets which can be set up using evolution strategies for dynamic conditions. If the chosen lowlight character in a given pattern has the probability λ, the length of the text is n and the length of the pattern is m. then we conjecture that the complexity of the new algorithm is Θ(n/λm).
  • Keywords
    computational complexity; pattern recognition; probability; statistical analysis; string matching; text analysis; Θ(n/λm) complexity; alphabets; dynamic conditions; evolution strategies; fast-string matching algorithm; lowlight characters; pattern length; pattern matching; pattern recognition; statistical probability table; text length; Probability;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Advanced Computational Intelligence (ICACI), 2015 Seventh International Conference on
  • Conference_Location
    Wuyi
  • Print_ISBN
    978-1-4799-7257-9
  • Type

    conf

  • DOI
    10.1109/ICACI.2015.7184773
  • Filename
    7184773