Ontology type: schema:ScholarlyArticle Open Access: True
2017-10
AUTHORSGregory Kucherov, Yakov Nekrich
ABSTRACTIn this paper we describe a data structure that supports pattern matching queries on a dynamically arriving text over an alphabet of constant size. Each new symbol can be prepended to T in O(1) worst-case time. At any moment, we can report all occurrences of a pattern P in the current text in O(|P|+k) time, where |P| is the length of P and k is the number of occurrences. This resolves, under assumption of constant size alphabet, a long-standing open problem of existence of a real-time indexing method for string matching (see Amir and Nor in Real-time indexing over fixed finite alphabets, pp. 1086–1095, 2008). More... »
PAGES387-400
http://scigraph.springernature.com/pub.10.1007/s00453-016-0199-7
DOIhttp://dx.doi.org/10.1007/s00453-016-0199-7
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1048466616
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/0801",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Artificial Intelligence and Image Processing",
"type": "DefinedTerm"
},
{
"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"
}
],
"author": [
{
"affiliation": {
"alternateName": "Laboratoire d'Informatique Gaspard-Monge",
"id": "https://www.grid.ac/institutes/grid.462940.d",
"name": [
"Laboratoire d\u2019Informatique Gaspard Monge, Universit\u00e9 Paris-Est & CNRS, Marne-la-Vall\u00e9e, France"
],
"type": "Organization"
},
"familyName": "Kucherov",
"givenName": "Gregory",
"id": "sg:person.013163701366.40",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013163701366.40"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "University of Waterloo",
"id": "https://www.grid.ac/institutes/grid.46078.3d",
"name": [
"Cheriton School of Computer Science, University of Waterloo, Waterloo, Canada"
],
"type": "Organization"
},
"familyName": "Nekrich",
"givenName": "Yakov",
"id": "sg:person.014556642366.63",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014556642366.63"
],
"type": "Person"
}
],
"citation": [
{
"id": "sg:pub.10.1007/3-540-08921-7_97",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1001138670",
"https://doi.org/10.1007/3-540-08921-7_97"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/322234.322244",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1002627098"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-21458-5_16",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1011929559",
"https://doi.org/10.1007/978-3-642-21458-5_16"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-21458-5_16",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1011929559",
"https://doi.org/10.1007/978-3-642-21458-5_16"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-31265-6_16",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1012866216",
"https://doi.org/10.1007/978-3-642-31265-6_16"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/11575832_9",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1017195072",
"https://doi.org/10.1007/11575832_9"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/11575832_9",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1017195072",
"https://doi.org/10.1007/11575832_9"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/1541885.1541889",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1017405123"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/s0022-0000(05)80064-9",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1017760034"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/28395.28434",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1022759585"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-24583-1_16",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1028745906",
"https://doi.org/10.1007/978-3-642-24583-1_16"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/195058.195170",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1037964780"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0890-5401(92)90034-d",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1045238564"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-319-19929-0_14",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1050208184",
"https://doi.org/10.1007/978-3-319-19929-0_14"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf01683268",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1053048814",
"https://doi.org/10.1007/bf01683268"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf01683268",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1053048814",
"https://doi.org/10.1007/bf01683268"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1137/s0097539700370539",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1062879236"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1137/1.9781611973099.84",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1088801552"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/focs.2012.79",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1095553984"
],
"type": "CreativeWork"
}
],
"datePublished": "2017-10",
"datePublishedReg": "2017-10-01",
"description": "In this paper we describe a data structure that supports pattern matching queries on a dynamically arriving text over an alphabet of constant size. Each new symbol can be prepended to T in O(1) worst-case time. At any moment, we can report all occurrences of a pattern P in the current text in O(|P|+k) time, where |P| is the length of P and k is the number of occurrences. This resolves, under assumption of constant size alphabet, a long-standing open problem of existence of a real-time indexing method for string matching (see Amir and Nor in Real-time indexing over fixed finite alphabets, pp. 1086\u20131095, 2008).",
"genre": "research_article",
"id": "sg:pub.10.1007/s00453-016-0199-7",
"inLanguage": [
"en"
],
"isAccessibleForFree": true,
"isPartOf": [
{
"id": "sg:journal.1047644",
"issn": [
"0178-4617",
"1432-0541"
],
"name": "Algorithmica",
"type": "Periodical"
},
{
"issueNumber": "2",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
"volumeNumber": "79"
}
],
"name": "Full-Fledged Real-Time Indexing for Constant Size Alphabets",
"pagination": "387-400",
"productId": [
{
"name": "readcube_id",
"type": "PropertyValue",
"value": [
"e6e2e2a700d28b29771aa4a0e3716637dbe53e72030279219faac0cbe9db4ea0"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s00453-016-0199-7"
]
},
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1048466616"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s00453-016-0199-7",
"https://app.dimensions.ai/details/publication/pub.1048466616"
],
"sdDataset": "articles",
"sdDatePublished": "2019-04-11T12:41",
"sdLicense": "https://scigraph.springernature.com/explorer/license/",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000363_0000000363/records_70053_00000002.jsonl",
"type": "ScholarlyArticle",
"url": "https://link.springer.com/10.1007%2Fs00453-016-0199-7"
}
]Download the RDF metadata as: json-ld nt turtle xml License info
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/s00453-016-0199-7'
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/s00453-016-0199-7'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-016-0199-7'
RDF/XML is a standard XML format for linked data.
curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-016-0199-7'
This table displays all metadata directly associated to this object as RDF triples.
126 TRIPLES
21 PREDICATES
43 URIs
19 LITERALS
7 BLANK NODES