An Optimal Algorithm for Online Square Detection View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2005

AUTHORS

Gen-Huey Chen , Jin-Ju Hong , Hsueh-I Lu

ABSTRACT

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. More... »

PAGES

280-287

Book

TITLE

Combinatorial Pattern Matching

ISBN

978-3-540-26201-5
978-3-540-31562-9

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11496656_24

DOI

http://dx.doi.org/10.1007/11496656_24

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1015847550


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Information Engineering, National Taiwan University", 
          "id": "http://www.grid.ac/institutes/grid.19188.39", 
          "name": [
            "Department of Computer Science and Information Engineering, National Taiwan University"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chen", 
        "givenName": "Gen-Huey", 
        "id": "sg:person.012627320571.90", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012627320571.90"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Information Engineering, National Taiwan University", 
          "id": "http://www.grid.ac/institutes/grid.19188.39", 
          "name": [
            "Department of Computer Science and Information Engineering, National Taiwan University"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Hong", 
        "givenName": "Jin-Ju", 
        "id": "sg:person.07671423646.12", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07671423646.12"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Information Engineering, National Taiwan University", 
          "id": "http://www.grid.ac/institutes/grid.19188.39", 
          "name": [
            "Department of Computer Science and Information Engineering, National Taiwan University"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lu", 
        "givenName": "Hsueh-I", 
        "id": "sg:person.013345515575.46", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013345515575.46"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2005", 
    "datePublishedReg": "2005-01-01", 
    "description": "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 \u03b2), where \u03b2 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.", 
    "editor": [
      {
        "familyName": "Apostolico", 
        "givenName": "Alberto", 
        "type": "Person"
      }, 
      {
        "familyName": "Crochemore", 
        "givenName": "Maxime", 
        "type": "Person"
      }, 
      {
        "familyName": "Park", 
        "givenName": "Kunsoo", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11496656_24", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-26201-5", 
        "978-3-540-31562-9"
      ], 
      "name": "Combinatorial Pattern Matching", 
      "type": "Book"
    }, 
    "keywords": [
      "time", 
      "detection problem", 
      "input string", 
      "number", 
      "detection", 
      "time complexity", 
      "optimal algorithm", 
      "non-empty strings", 
      "algorithm", 
      "problem", 
      "prefix", 
      "square detection", 
      "strings", 
      "concatenation", 
      "complexity", 
      "squares", 
      "distinct character", 
      "character", 
      "Leung", 
      "Peng", 
      "Ting"
    ], 
    "name": "An Optimal Algorithm for Online Square Detection", 
    "pagination": "280-287", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1015847550"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11496656_24"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11496656_24", 
      "https://app.dimensions.ai/details/publication/pub.1015847550"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-10T10:44", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/chapter/chapter_253.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/11496656_24"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/11496656_24'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/11496656_24'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11496656_24'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11496656_24'


 

This table displays all metadata directly associated to this object as RDF triples.

105 TRIPLES      23 PREDICATES      47 URIs      40 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11496656_24 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N437e636c102c465a8f70677f00a5903b
4 schema:datePublished 2005
5 schema:datePublishedReg 2005-01-01
6 schema:description 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.
7 schema:editor Nee79b2f47d2048049c03b0012f421fce
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Ncc6ce055a7734d289d9d8814e78963c5
12 schema:keywords Leung
13 Peng
14 Ting
15 algorithm
16 character
17 complexity
18 concatenation
19 detection
20 detection problem
21 distinct character
22 input string
23 non-empty strings
24 number
25 optimal algorithm
26 prefix
27 problem
28 square detection
29 squares
30 strings
31 time
32 time complexity
33 schema:name An Optimal Algorithm for Online Square Detection
34 schema:pagination 280-287
35 schema:productId N60e02477f4f04a04bf85b802a896f94e
36 N6aa68c5e0cd24cd4b98bb14ef13be5b8
37 schema:publisher N4da11899866f451e92290166b249c195
38 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015847550
39 https://doi.org/10.1007/11496656_24
40 schema:sdDatePublished 2022-05-10T10:44
41 schema:sdLicense https://scigraph.springernature.com/explorer/license/
42 schema:sdPublisher N07530587141a4052a6fa0b300da92a16
43 schema:url https://doi.org/10.1007/11496656_24
44 sgo:license sg:explorer/license/
45 sgo:sdDataset chapters
46 rdf:type schema:Chapter
47 N0204993c7ad746f6a6529d484f514ab4 rdf:first N33dbad75778e4555a446f0b8be2c7385
48 rdf:rest rdf:nil
49 N07530587141a4052a6fa0b300da92a16 schema:name Springer Nature - SN SciGraph project
50 rdf:type schema:Organization
51 N1b7fe5cad1134daf879edaf0fd794cb5 schema:familyName Crochemore
52 schema:givenName Maxime
53 rdf:type schema:Person
54 N2a847e7b344d49b5ac865a3bb969206e rdf:first sg:person.013345515575.46
55 rdf:rest rdf:nil
56 N33dbad75778e4555a446f0b8be2c7385 schema:familyName Park
57 schema:givenName Kunsoo
58 rdf:type schema:Person
59 N437e636c102c465a8f70677f00a5903b rdf:first sg:person.012627320571.90
60 rdf:rest Na5c0ea1a1f8d40a39d4526d05173ad2f
61 N4da11899866f451e92290166b249c195 schema:name Springer Nature
62 rdf:type schema:Organisation
63 N60e02477f4f04a04bf85b802a896f94e schema:name doi
64 schema:value 10.1007/11496656_24
65 rdf:type schema:PropertyValue
66 N6aa68c5e0cd24cd4b98bb14ef13be5b8 schema:name dimensions_id
67 schema:value pub.1015847550
68 rdf:type schema:PropertyValue
69 Na5c0ea1a1f8d40a39d4526d05173ad2f rdf:first sg:person.07671423646.12
70 rdf:rest N2a847e7b344d49b5ac865a3bb969206e
71 Nb9252fc1591541f2b027763b71a3639a schema:familyName Apostolico
72 schema:givenName Alberto
73 rdf:type schema:Person
74 Ncc6ce055a7734d289d9d8814e78963c5 schema:isbn 978-3-540-26201-5
75 978-3-540-31562-9
76 schema:name Combinatorial Pattern Matching
77 rdf:type schema:Book
78 Nee79b2f47d2048049c03b0012f421fce rdf:first Nb9252fc1591541f2b027763b71a3639a
79 rdf:rest Nf741ad725e27432d83bef2dc11f426d1
80 Nf741ad725e27432d83bef2dc11f426d1 rdf:first N1b7fe5cad1134daf879edaf0fd794cb5
81 rdf:rest N0204993c7ad746f6a6529d484f514ab4
82 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
83 schema:name Information and Computing Sciences
84 rdf:type schema:DefinedTerm
85 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
86 schema:name Artificial Intelligence and Image Processing
87 rdf:type schema:DefinedTerm
88 sg:person.012627320571.90 schema:affiliation grid-institutes:grid.19188.39
89 schema:familyName Chen
90 schema:givenName Gen-Huey
91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012627320571.90
92 rdf:type schema:Person
93 sg:person.013345515575.46 schema:affiliation grid-institutes:grid.19188.39
94 schema:familyName Lu
95 schema:givenName Hsueh-I
96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013345515575.46
97 rdf:type schema:Person
98 sg:person.07671423646.12 schema:affiliation grid-institutes:grid.19188.39
99 schema:familyName Hong
100 schema:givenName Jin-Ju
101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07671423646.12
102 rdf:type schema:Person
103 grid-institutes:grid.19188.39 schema:alternateName Department of Computer Science and Information Engineering, National Taiwan University
104 schema:name Department of Computer Science and Information Engineering, National Taiwan University
105 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...