• DocumentCode
    3553456
  • Title

    A representation scheme and a searching algorithm for repetitions in a string

  • Author

    Lee, Edward T. ; Ho, Tin Kam

  • Author_Institution
    Dept. of Electr. & Comput. Eng., Florida Int. Univ., Miami, FL, USA
  • fYear
    1991
  • fDate
    7-10 Apr 1991
  • Firstpage
    55
  • Abstract
    A representation scheme and a searching algorithm for all repetitions of the form xx in a finite string are presented. The algorithm is based on a careful arrangement of comparisons of adjacent substrings, with several important considerations to eliminate unnecessary steps. A divide-and-conquer strategy is used to reduce the problem size significantly. The run-time is O(n log n), and may be O(n) for some types of input. Possible further developments and applications are discussed
  • Keywords
    computational complexity; search problems; divide-and-conquer; finite string; repetitions; representation scheme; run-time; searching algorithm; Computer science; Contracts; Linearity; Runtime; Tin;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Southeastcon '91., IEEE Proceedings of
  • Conference_Location
    Williamsburg, VA
  • Print_ISBN
    0-7803-0033-5
  • Type

    conf

  • DOI
    10.1109/SECON.1991.147703
  • Filename
    147703
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3553456