| dbo:abstract
|
- Das LCP-Array ist eine Datenstruktur aus der Informatik, welche meist in Kombination mit dem Suffixarray verwendet wird. Die Bezeichnung „LCP“ ist eine Abkürzung für „longest common prefix“ (dt. längstes gemeinsames Präfix). Das Array selbst enthält die Länge des längsten gemeinsamen Präfixes von je zwei lexikographisch aufeinanderfolgenden Suffixen. Für das LCP-Array gibt es zahlreiche Anwendungen aus dem Bereich der Textsuche und -indizierung, wie beispielsweise die Konstruktion des Suffixbaums oder eine effiziente Suche aller Vorkommen eines Suchmusters in einem Text. Der benötigte Speicherplatz des LCP-Arrays ist linear im Vergleich zur Textgröße und es gibt Algorithmen, die das LCP-Array in linearer Zeit mit Hilfe des Suffixarrays konstruieren. Es wurde erstmals in einer Veröffentlichung von Manber und Myers (1993) benutzt, in der es als Hgt-Array bezeichnet wurde. (de)
- In computer science, the longest common prefix array (LCP array) is an auxiliary data structure to the suffix array. It stores the lengths of the longest common prefixes (LCPs) between all pairs of consecutive suffixes in a sorted suffix array. For example, if A := [aab, ab, abaab, b, baab] is a suffix array, the longest common prefix between A[1] = aab and A[2] = ab is a which has length 1, so H[2] = 1 in the LCP array H. Likewise, the LCP of A[2] = ab and A[3] = abaab is ab, so H[3] = 2. Augmenting the suffix array with the LCP array allows one to efficiently simulate top-down and bottom-up traversals of the suffix tree, speeds up pattern matching on the suffix array and is a prerequisite for compressed suffix trees. (en)
- LCP배열 (Longest Common Prefix array, 최장 공통 접두사 배열)은 접미사 배열에서 이전 접미사와 공통되는 접두사의 길이를 저장한 배열이다. (ko)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 29061 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:above
| |
| dbp:data
| |
| dbp:date
| |
| dbp:header
| |
| dbp:headerstyle
| |
| dbp:label
| |
| dbp:reason
|
- this section is a straight-up copy of a StackOverflow answer so it has the form of a reply to a question. (en)
|
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- LCP배열 (Longest Common Prefix array, 최장 공통 접두사 배열)은 접미사 배열에서 이전 접미사와 공통되는 접두사의 길이를 저장한 배열이다. (ko)
- Das LCP-Array ist eine Datenstruktur aus der Informatik, welche meist in Kombination mit dem Suffixarray verwendet wird. Die Bezeichnung „LCP“ ist eine Abkürzung für „longest common prefix“ (dt. längstes gemeinsames Präfix). Das Array selbst enthält die Länge des längsten gemeinsamen Präfixes von je zwei lexikographisch aufeinanderfolgenden Suffixen. (de)
- In computer science, the longest common prefix array (LCP array) is an auxiliary data structure to the suffix array. It stores the lengths of the longest common prefixes (LCPs) between all pairs of consecutive suffixes in a sorted suffix array. For example, if A := [aab, ab, abaab, b, baab] is a suffix array, the longest common prefix between A[1] = aab and A[2] = ab is a which has length 1, so H[2] = 1 in the LCP array H. Likewise, the LCP of A[2] = ab and A[3] = abaab is ab, so H[3] = 2. (en)
|
| rdfs:label
|
- LCP-Array (de)
- LCP array (en)
- LCP 배열 (ko)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
