{"data":{"id":"10.48550/arxiv.1001.2101","type":"dois","attributes":{"doi":"10.48550/arxiv.1001.2101","prefix":"10.48550","suffix":"arxiv.1001.2101","identifiers":[{"identifier":"1001.2101","identifierType":"arXiv"}],"alternateIdentifiers":[{"alternateIdentifierType":"arXiv","alternateIdentifier":"1001.2101"}],"creators":[{"name":"Sirén, Jouni","nameType":"Personal","givenName":"Jouni","familyName":"Sirén","affiliation":[],"nameIdentifiers":[]}],"titles":[{"title":"Sampled Longest Common Prefix Array"}],"publisher":"arXiv","container":{},"publicationYear":2010,"subjects":[{"lang":"en","subject":"Data Structures and Algorithms (cs.DS)","subjectScheme":"arXiv"},{"subject":"FOS: Computer and information sciences","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"FOS: Computer and information sciences","schemeUri":"http://www.oecd.org/science/inno/38235147.pdf","subjectScheme":"Fields of Science and Technology (FOS)"}],"contributors":[],"dates":[{"date":"2010-01-13T09:18:24Z","dateType":"Submitted","dateInformation":"v1"},{"date":"2010-01-14T08:36:27Z","dateType":"Updated","dateInformation":"v1"},{"date":"2010-03-29T16:18:11Z","dateType":"Submitted","dateInformation":"v2"},{"date":"2010-03-30T00:03:55Z","dateType":"Updated","dateInformation":"v2"},{"date":"2010-06-29T11:07:23Z","dateType":"Submitted","dateInformation":"v3"},{"date":"2010-06-30T00:01:13Z","dateType":"Updated","dateInformation":"v3"},{"date":"2010-01","dateType":"Available","dateInformation":"v1"},{"date":"2010","dateType":"Issued"}],"language":null,"types":{"ris":"RPRT","bibtex":"article","citeproc":"article-journal","schemaOrg":"ScholarlyArticle","resourceType":"Article","resourceTypeGeneral":"Text"},"relatedIdentifiers":[{"relationType":"IsVersionOf","relatedIdentifier":"10.1007/978-3-642-13509-5_21","relatedIdentifierType":"DOI"}],"relatedItems":[],"sizes":[],"formats":[],"version":"3","rightsList":[{"rights":"arXiv.org perpetual, non-exclusive license","rightsUri":"http://arxiv.org/licenses/nonexclusive-distrib/1.0/"}],"descriptions":[{"description":"When augmented with the longest common prefix (LCP) array and some other structures, the suffix array can solve many string processing problems in optimal time and space. A compressed representation of the LCP array is also one of the main building blocks in many compressed suffix tree proposals. In this paper, we describe a new compressed LCP representation: the sampled LCP array. We show that when used with a compressed suffix array (CSA), the sampled LCP array often offers better time/space trade-offs than the existing alternatives. We also show how to construct the compressed representations of the LCP array directly from a CSA.","descriptionType":"Abstract"},{"description":"This is a slightly extended version of the paper that was presented at CPM 2010. The implementation is available at http://www.cs.helsinki.fi/group/suds/rlcsa/","descriptionType":"Other"}],"geoLocations":[],"fundingReferences":[],"xml":"PD94bWwgdmVyc2lvbj0iMS4wIiBlbmNvZGluZz0idXRmLTgiPz4KPHJlc291cmNlIHhtbG5zPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCIgeG1sbnM6eHNpPSJodHRwOi8vd3d3LnczLm9yZy8yMDAxL1hNTFNjaGVtYS1pbnN0YW5jZSIgeHNpOnNjaGVtYUxvY2F0aW9uPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCBodHRwOi8vc2NoZW1hLmRhdGFjaXRlLm9yZy9tZXRhL2tlcm5lbC00LjMvbWV0YWRhdGEueHNkIj4KICA8aWRlbnRpZmllciBpZGVudGlmaWVyVHlwZT0iRE9JIj4xMC40ODU1MC9BUlhJVi4xMDAxLjIxMDE8L2lkZW50aWZpZXI+CiAgPGFsdGVybmF0ZUlkZW50aWZpZXJzPgogICAgPGFsdGVybmF0ZUlkZW50aWZpZXIgYWx0ZXJuYXRlSWRlbnRpZmllclR5cGU9ImFyWGl2Ij4xMDAxLjIxMDE8L2FsdGVybmF0ZUlkZW50aWZpZXI+CiAgPC9hbHRlcm5hdGVJZGVudGlmaWVycz4KICA8Y3JlYXRvcnM+CiAgICA8Y3JlYXRvcj4KICAgICAgPGNyZWF0b3JOYW1lIG5hbWVUeXBlPSJQZXJzb25hbCI+U2lyw6luLCBKb3VuaTwvY3JlYXRvck5hbWU+CiAgICAgIDxnaXZlbk5hbWU+Sm91bmk8L2dpdmVuTmFtZT4KICAgICAgPGZhbWlseU5hbWU+U2lyw6luPC9mYW1pbHlOYW1lPgogICAgPC9jcmVhdG9yPgogIDwvY3JlYXRvcnM+CiAgPHRpdGxlcz4KICAgIDx0aXRsZT5TYW1wbGVkIExvbmdlc3QgQ29tbW9uIFByZWZpeCBBcnJheTwvdGl0bGU+CiAgPC90aXRsZXM+CiAgPHB1Ymxpc2hlcj5hclhpdjwvcHVibGlzaGVyPgogIDxwdWJsaWNhdGlvblllYXI+MjAxMDwvcHVibGljYXRpb25ZZWFyPgogIDxzdWJqZWN0cz4KICAgIDxzdWJqZWN0IHhtbDpsYW5nPSJlbiIgc3ViamVjdFNjaGVtZT0iYXJYaXYiPkRhdGEgU3RydWN0dXJlcyBhbmQgQWxnb3JpdGhtcyAoY3MuRFMpPC9zdWJqZWN0PgogICAgPHN1YmplY3Qgc3ViamVjdFNjaGVtZT0iRmllbGRzIG9mIFNjaWVuY2UgYW5kIFRlY2hub2xvZ3kgKEZPUykiPkZPUzogQ29tcHV0ZXIgYW5kIGluZm9ybWF0aW9uIHNjaWVuY2VzPC9zdWJqZWN0PgogIDwvc3ViamVjdHM+CiAgPGRhdGVzPgogICAgPGRhdGUgZGF0ZVR5cGU9IlN1Ym1pdHRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2MSI+MjAxMC0wMS0xM1QwOToxODoyNFo8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iVXBkYXRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2MSI+MjAxMC0wMS0xNFQwODozNjoyN1o8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iU3VibWl0dGVkIiBkYXRlSW5mb3JtYXRpb249InYyIj4yMDEwLTAzLTI5VDE2OjE4OjExWjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJVcGRhdGVkIiBkYXRlSW5mb3JtYXRpb249InYyIj4yMDEwLTAzLTMwVDAwOjAzOjU1WjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJTdWJtaXR0ZWQiIGRhdGVJbmZvcm1hdGlvbj0idjMiPjIwMTAtMDYtMjlUMTE6MDc6MjNaPC9kYXRlPgogICAgPGRhdGUgZGF0ZVR5cGU9IlVwZGF0ZWQiIGRhdGVJbmZvcm1hdGlvbj0idjMiPjIwMTAtMDYtMzBUMDA6MDE6MTNaPC9kYXRlPgogICAgPGRhdGUgZGF0ZVR5cGU9IkF2YWlsYWJsZSIgZGF0ZUluZm9ybWF0aW9uPSJ2MSI+MjAxMC0wMTwvZGF0ZT4KICA8L2RhdGVzPgogIDxyZXNvdXJjZVR5cGUgcmVzb3VyY2VUeXBlR2VuZXJhbD0iVGV4dCI+QXJ0aWNsZTwvcmVzb3VyY2VUeXBlPgogIDxyZWxhdGVkSWRlbnRpZmllcnM+CiAgICA8cmVsYXRlZElkZW50aWZpZXIgcmVsYXRlZElkZW50aWZpZXJUeXBlPSJET0kiIHJlbGF0aW9uVHlwZT0iSXNWZXJzaW9uT2YiPjEwLjEwMDcvOTc4LTMtNjQyLTEzNTA5LTVfMjE8L3JlbGF0ZWRJZGVudGlmaWVyPgogIDwvcmVsYXRlZElkZW50aWZpZXJzPgogIDx2ZXJzaW9uPjM8L3ZlcnNpb24+CiAgPHJpZ2h0c0xpc3Q+CiAgICA8cmlnaHRzIHJpZ2h0c1VSST0iaHR0cDovL2FyeGl2Lm9yZy9saWNlbnNlcy9ub25leGNsdXNpdmUtZGlzdHJpYi8xLjAvIj5hclhpdi5vcmcgcGVycGV0dWFsLCBub24tZXhjbHVzaXZlIGxpY2Vuc2U8L3JpZ2h0cz4KICA8L3JpZ2h0c0xpc3Q+CiAgPGRlc2NyaXB0aW9ucz4KICAgIDxkZXNjcmlwdGlvbiBkZXNjcmlwdGlvblR5cGU9IkFic3RyYWN0Ij5XaGVuIGF1Z21lbnRlZCB3aXRoIHRoZSBsb25nZXN0IGNvbW1vbiBwcmVmaXggKExDUCkgYXJyYXkgYW5kIHNvbWUgb3RoZXIgc3RydWN0dXJlcywgdGhlIHN1ZmZpeCBhcnJheSBjYW4gc29sdmUgbWFueSBzdHJpbmcgcHJvY2Vzc2luZyBwcm9ibGVtcyBpbiBvcHRpbWFsIHRpbWUgYW5kIHNwYWNlLiBBIGNvbXByZXNzZWQgcmVwcmVzZW50YXRpb24gb2YgdGhlIExDUCBhcnJheSBpcyBhbHNvIG9uZSBvZiB0aGUgbWFpbiBidWlsZGluZyBibG9ja3MgaW4gbWFueSBjb21wcmVzc2VkIHN1ZmZpeCB0cmVlIHByb3Bvc2Fscy4gSW4gdGhpcyBwYXBlciwgd2UgZGVzY3JpYmUgYSBuZXcgY29tcHJlc3NlZCBMQ1AgcmVwcmVzZW50YXRpb246IHRoZSBzYW1wbGVkIExDUCBhcnJheS4gV2Ugc2hvdyB0aGF0IHdoZW4gdXNlZCB3aXRoIGEgY29tcHJlc3NlZCBzdWZmaXggYXJyYXkgKENTQSksIHRoZSBzYW1wbGVkIExDUCBhcnJheSBvZnRlbiBvZmZlcnMgYmV0dGVyIHRpbWUvc3BhY2UgdHJhZGUtb2ZmcyB0aGFuIHRoZSBleGlzdGluZyBhbHRlcm5hdGl2ZXMuIFdlIGFsc28gc2hvdyBob3cgdG8gY29uc3RydWN0IHRoZSBjb21wcmVzc2VkIHJlcHJlc2VudGF0aW9ucyBvZiB0aGUgTENQIGFycmF5IGRpcmVjdGx5IGZyb20gYSBDU0EuPC9kZXNjcmlwdGlvbj4KICAgIDxkZXNjcmlwdGlvbiBkZXNjcmlwdGlvblR5cGU9Ik90aGVyIj5UaGlzIGlzIGEgc2xpZ2h0bHkgZXh0ZW5kZWQgdmVyc2lvbiBvZiB0aGUgcGFwZXIgdGhhdCB3YXMgcHJlc2VudGVkIGF0IENQTSAyMDEwLiBUaGUgaW1wbGVtZW50YXRpb24gaXMgYXZhaWxhYmxlIGF0IGh0dHA6Ly93d3cuY3MuaGVsc2lua2kuZmkvZ3JvdXAvc3Vkcy9ybGNzYS88L2Rlc2NyaXB0aW9uPgogIDwvZGVzY3JpcHRpb25zPgo8L3Jlc291cmNlPg==","url":"https://arxiv.org/abs/1001.2101","contentUrl":null,"metadataVersion":0,"schemaVersion":"http://datacite.org/schema/kernel-4","source":"mds","isActive":true,"state":"findable","reason":null,"viewCount":0,"viewsOverTime":[],"downloadCount":0,"downloadsOverTime":[],"referenceCount":0,"citationCount":0,"citationsOverTime":[],"partCount":0,"partOfCount":0,"versionCount":0,"versionOfCount":0,"created":"2022-03-15T19:50:06.000Z","registered":"2022-03-15T19:50:07.000Z","published":"2010","updated":"2022-03-15T19:50:07.000Z"},"relationships":{"client":{"data":{"id":"arxiv.content","type":"clients"}},"provider":{"data":{"id":"arxiv","type":"providers"}},"media":{"data":{"id":"10.48550/arxiv.1001.2101","type":"media"}},"references":{"data":[]},"citations":{"data":[]},"parts":{"data":[]},"partOf":{"data":[]},"versions":{"data":[]},"versionOf":{"data":[]}}}}