An Optimal Algorithm for Online Square Detection | Zendy

Gen-Huey Chen | Zendy; Jin-Ju Hong | Zendy; Hsueh-I Lu | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

An Optimal Algorithm for Online Square Detection

Author(s) -

Gen-Huey Chen,

Jin-Ju Hong,

Hsueh-I Lu

Publication year - 2005

Publication title -

lecture notes in computer science

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 0.249

H-Index - 400

eISSN - 1611-3349

pISSN - 0302-9743

ISBN - 3-540-26201-6

DOI - 10.1007/11496656_24

Subject(s) - concatenation (mathematics) , square (algebra) , character (mathematics) , prefix , string (physics) , algorithm , combinatorics , integer (computer science) , computer science , time complexity , mathematics , discrete mathematics , philosophy , linguistics , geometry , mathematical physics , programming language

A square is the concatenation of two identical non-empty strings. Let S be the input string which is given character by character. Let m be the (unknown) smallest integer such that the m-th prefix of S contains a square. The online square detection problem is to determine m as soon as the m-th character of S is read. The best previously known algorithm of the online square detection problem, due to Leung, Peng, and Ting, runs in O(mlog2m) time. We improve the time complexity to O(mlog β), where β is the number of distinct characters in the m-th prefix of the input string. It is not difficult to implement our algorithm to run in expected O(m) time.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research