2792:
970:
2592:
397:
4241:
829:
2787:{\displaystyle \pi _{\Sigma }(s)={\begin{cases}\varepsilon &{\mbox{if }}s=\varepsilon {\mbox{ the empty string}}\\\pi _{\Sigma }(t)&{\mbox{if }}s=ta{\mbox{ and }}a\notin \Sigma \\\pi _{\Sigma }(t)a&{\mbox{if }}s=ta{\mbox{ and }}a\in \Sigma \end{cases}}}
4043:
4354:
3793:
3086:
280:
4470:
4087:
1169:
1228:
3541:
2922:
706:
3911:
578:
965:{\displaystyle D=\{\langle 0\rangle ,\langle 1\rangle ,\langle 2\rangle ,\langle 3\rangle ,\langle 4\rangle ,\langle 5\rangle ,\langle 6\rangle ,\langle 7\rangle ,\langle 8\rangle ,\langle 9\rangle \}}
206:
1515:
are closed under string substitution. That is, if each character in the alphabet of a regular language is substituted by another regular language, the result is still a regular language. Similarly,
821:
272:
4571:
3831:
3245:
2094:
759:
3126:
2291:
The class of regular languages is closed under homomorphisms and inverse homomorphisms. Similarly, the context-free languages are closed under homomorphisms and inverse homomorphisms.
4398:
1998:
1507:
3935:
1057:
4252:
3599:
2264:
2206:
3684:
2327:
1266:
2990:
2584:
2150:
627:
1325:
1002:
4526:
4616:
Although every regular language is also context-free, the previous theorem is not implied by the current one, since the former yields a shaper result for regular languages.
4500:
2815:
73:
4664:
3403:
3155:
470:
139:
3676:
2547:
2519:
2351:
392:{\displaystyle (\langle b\rangle \cdot \langle l\rangle )\cdot (\varepsilon \cdot \langle ah\rangle )=\langle bl\rangle \cdot \langle ah\rangle =\langle blah\rangle }
4072:
1768:
598:
1876:
650:
2978:
162:
4236:{\displaystyle \operatorname {Pref} (L)=\bigcup _{s\in L}\operatorname {Pref} _{L}(s)=\left\{t\ \vert \ s=tu;s\in L;t,u\in \operatorname {Alph} (L)^{*}\right\}}
3423:
3175:
2286:
2020:
1924:
1900:
1847:
1808:
1788:
1289:
1103:
1083:
510:
490:
444:
424:
113:
93:
4586:
4413:
406:
is a finite or infinite set of strings. Besides the usual set operations like union, intersection etc., concatenation can be applied to languages: if both
1108:
3546:
The relation is clearly of finite index (has a finite number of equivalence classes) if and only if the family right quotients is finite; that is, if
43:, and some commonly used functions in the theoretical realm are rarely used when programming. This article defines some of these basic terms.
1177:
3446:
2845:
5099:
655:
4994:
3846:
5033:
515:
4959:
4964:
4799:
167:
4706:
4969:
764:
215:
5221:
5180:
4954:
4531:
5048:
4989:
4861:
3804:
3183:
4896:
4596:
2822:
2027:
711:
4038:{\displaystyle \operatorname {Pref} _{L}(s)=\{t\ \vert \ s=tu{\mbox{ for }}t,u\in \operatorname {Alph} (L)^{*}\}}
3097:
4365:
4349:{\displaystyle L=\left\{abc\right\}{\mbox{ then }}\operatorname {Pref} (L)=\left\{\varepsilon ,a,ab,abc\right\}}
1931:
1452:
1355:
that maps characters in Σ to languages (possibly in a different alphabet). Thus, for example, given a character
5076:
2481:
A very simple string homomorphism example that maps each character to just a character is the conversion of an
3788:{\displaystyle (sa)\div b={\begin{cases}s&{\mbox{if }}a=b\\(s\div b)a&{\mbox{if }}a\neq b\end{cases}}}
1030:
3552:
2215:
2157:
17:
3081:{\displaystyle (sa)/b={\begin{cases}s&{\mbox{if }}a=b\\\varepsilon &{\mbox{if }}a\neq b\end{cases}}}
5081:
4936:
2297:
1233:
5216:
5160:
4886:
2552:
1340:
1021:
403:
2101:
5165:
5043:
5010:
4946:
606:
5211:
5175:
5071:
5015:
4916:
4870:
3926:
1298:
975:
4505:
3714:
3022:
2623:
5170:
4974:
4906:
4485:
2800:
1728:
58:
5119:
4628:
3382:
3134:
3617:
1732:
32:
449:
118:
5124:
5066:
4926:
4854:
3655:
3357:
3342:
The left quotient (when defined similar to
Hopcroft and Ullman 1979) of a singleton language
2532:
2504:
2336:
1735:) is a string substitution such that each character is replaced by a single string. That is,
1516:
1004:. The set of all decimal numbers of arbitrary length is an example for an infinite language.
4051:
1738:
583:
4931:
3837:
3426:
1826:
40:
4716:
1852:
632:
8:
5129:
2955:
2354:
4625:
Strictly formally, a homomorphism yields a language consisting of just one string, i.e.
4465:{\displaystyle \operatorname {Pref} (\operatorname {Pref} (L))=\operatorname {Pref} (L)}
144:
5058:
5025:
4825:
3432:
3408:
3368:
3160:
2271:
2005:
1909:
1885:
1832:
1793:
1773:
1274:
1088:
1068:
495:
475:
429:
409:
98:
78:
4702:
4695:
4829:
5185:
5155:
5109:
4911:
4847:
4815:
4712:
3621:
3613:
1822:
1512:
629:
consisting of just the empty string is to be distinguished from the empty language
36:
28:
1164:{\displaystyle \operatorname {Alph} (S)=\bigcup _{s\in S}\operatorname {Alph} (s)}
5038:
4979:
4891:
4591:
4480:
2833:
1814:
1714:({ ‹Straße›, ‹u2›, ‹Go!› }) = { ‹STRASSE› } ∪ { ‹U› } ∪ { } = { ‹STRASSE›, ‹U› }.
1388:
is some language whose alphabet is Δ. This mapping may be extended to strings as
3253:
may be defined similarly, with operations taking place on the left of a string.
2392:
be undefined on punctuation chars. Examples for inverse homomorphic images are
5091:
4984:
3339:, Hopcroft's and Ullman's definition implies yielding {}, rather than { ε }.
5205:
4901:
4878:
2586:. It is formally defined by removal of characters from the right hand side:
3327:. This is not a generalization of the above definition, since, for a string
5104:
4921:
4574:
2818:
1400:
52:
4820:
4803:
1675:(‹Straße›) = {‹S›} ⋅ {‹T›} ⋅ {‹R›} ⋅ {‹A›} ⋅ {‹SS›} ⋅ {‹E›} = {‹STRASSE›},
1016:
is the set of all of the characters that occur in a particular string. If
5114:
4599:— definition and implementation of more basic operations on strings
1818:
1386:
1223:{\displaystyle \{\langle a\rangle ,\langle c\rangle ,\langle o\rangle \}}
209:
708:, while concatenating with the latter always yields the empty language:
4404:
3536:{\displaystyle \sim _{S}\;\,=\,\{(s,t)\in M\times M\ \vert \ S/s=S/t\}}
2917:{\displaystyle \pi _{\Sigma }(L)=\{\pi _{\Sigma }(s)\ \vert \ s\in L\}}
2529:
is the string that results by removing all characters that are not in
652:. Concatenating any language with the former doesn't make any change:
1446:∈ Σ. String substitutions may be extended to entire languages as
5150:
701:{\displaystyle S\cdot \{\varepsilon \}=S=\{\varepsilon \}\cdot S}
3906:{\displaystyle \pi _{\Sigma }(s)\div a=\pi _{\Sigma }(s\div a)}
2482:
2984:
on the right hand side, the result is the empty string. Thus:
2486:
39:; however, the notation used is different from that used for
972:, the set of all three-digit decimal numbers is obtained as
573:{\displaystyle S\cdot T=\{s\cdot t\mid s\in S\land t\in T\}}
5134:
3781:
3074:
2780:
472:
is defined as the set of concatenations of any string from
164:. Concatenating with the empty string makes no difference:
4839:
4697:
Introduction to
Automata Theory, Languages and Computation
2821:. The projection of a string is essentially the same as a
2294:
A string homomorphism is said to be ε-free (or e-free) if
1085:
is the set of all characters that occur in any string of
201:{\displaystyle s\cdot \varepsilon =s=\varepsilon \cdot s}
3644:
is the removal of the first occurrence of the character
3620:. This is discussed in greater detail in the article on
1529:(.) to uppercase, which may be defined e.g. as follows:
4587:
Comparison of programming languages (string functions)
4282:
3992:
3763:
3723:
3652:, starting from the right hand side. It is denoted as
3056:
3031:
2762:
2743:
2699:
2680:
2648:
2632:
2471:({ ‹a› }) = { ‹A› } ≠ { ‹A›, ‹bb› }. The homomorphism
4780:
Hopcroft, Ullman (1979), Sect.6.2, Theorem 6.3, p.132
4753:
Hopcroft, Ullman (1979), Sect.6.2, Theorem 6.2, p.131
4701:. Reading, Massachusetts: Addison-Wesley Publishing.
4631:
4534:
4508:
4488:
4416:
4368:
4255:
4090:
4054:
3938:
3849:
3807:
3687:
3658:
3555:
3449:
3411:
3385:
3186:
3163:
3137:
3100:
2993:
2958:
2848:
2803:
2595:
2555:
2535:
2507:
2339:
2300:
2274:
2218:
2160:
2104:
2030:
2008:
1934:
1912:
1888:
1855:
1835:
1796:
1776:
1741:
1455:
1301:
1277:
1236:
1180:
1111:
1091:
1071:
1033:
978:
832:
767:
714:
658:
635:
609:
586:
518:
498:
478:
452:
432:
412:
283:
218:
170:
147:
121:
101:
81:
61:
4798:
4771:
Hopcroft, Ullman (1979), Sect.3.2, Theorem 3.5, p.61
4744:
Hopcroft, Ullman (1979), Sect.3.2, Theorem 3.4, p.60
1620:
no uppercase char available, map to two-char string
1582:map lowercase char to corresponding uppercase char
1327:as well as of the language of all decimal numbers.
816:{\displaystyle S\cdot (T\cdot U)=(S\cdot T)\cdot U}
267:{\displaystyle s\cdot (t\cdot u)=(s\cdot t)\cdot u}
4694:
4658:
4565:
4520:
4494:
4464:
4392:
4348:
4235:
4066:
4037:
3905:
3825:
3787:
3670:
3616:, that is, a language that can be recognized by a
3593:
3535:
3417:
3397:
3239:
3169:
3149:
3120:
3080:
2972:
2916:
2809:
2786:
2578:
2541:
2513:
2345:
2321:
2280:
2258:
2200:
2144:
2088:
2014:
2002:while the inverse homomorphic image of a language
1992:
1918:
1894:
1870:
1841:
1802:
1782:
1762:
1501:
1319:
1283:
1260:
1222:
1163:
1097:
1077:
1051:
996:
964:
815:
753:
700:
644:
621:
592:
572:
504:
484:
464:
438:
418:
391:
266:
200:
156:
133:
107:
87:
67:
4566:{\displaystyle s\in \operatorname {Pref} _{L}(t)}
51:A string is a finite sequence of characters. The
5203:
2367:can also be obtained by defining similar to the
3929:to a string, with respect to a given language:
3826:{\displaystyle \varepsilon \div a=\varepsilon }
3256:Hopcroft and Ullman (1979) define the quotient
3240:{\displaystyle S/a=\{s\in M\ \vert \ sa\in S\}}
3091:The quotient of the empty string may be taken:
2357:are examples of (ε-free) string homomorphisms.
4693:Hopcroft, John E.; Ullman, Jeffrey D. (1979).
4692:
4855:
4619:
4573:. This relation is a particular example of a
2952:, from the right hand side. It is denoted as
2439:(‹a›) = ‹A›, while ‹bb› cannot be reached by
2089:{\displaystyle f^{-1}(L)=\{s\mid f(s)\in L\}}
761:. Concatenation of languages is associative:
4653:
4647:
4161:
4032:
3973:
3964:
3588:
3573:
3556:
3530:
3499:
3466:
3234:
3216:
3201:
2911:
2896:
2871:
2478:is not ε-free, since it maps e.g. ‹0› to ε.
2083:
2056:
1987:
1960:
1255:
1237:
1217:
1214:
1208:
1202:
1196:
1190:
1184:
1181:
959:
956:
950:
944:
938:
932:
926:
920:
914:
908:
902:
896:
890:
884:
878:
872:
866:
860:
854:
848:
842:
839:
754:{\displaystyle S\cdot \{\}=\{\}=\{\}\cdot S}
742:
739:
733:
730:
724:
721:
689:
683:
671:
665:
639:
636:
616:
610:
567:
531:
386:
371:
365:
356:
350:
341:
332:
323:
305:
299:
293:
287:
3836:Clearly, right cancellation and projection
3608:is the monoid of words over some alphabet,
3121:{\displaystyle \varepsilon /a=\varepsilon }
2402:({ ‹SSS› }) = { ‹sss›, ‹sß›, ‹ßs› }, since
4862:
4848:
4762:Hopcroft, Ullman (1979), Sect.3.2, p.60-61
4393:{\displaystyle \operatorname {Pref} (L)=L}
3460:
2927:
1993:{\displaystyle f^{-1}(s)=\{w\mid f(w)=s\}}
1642:forbid punctuation, map to empty language
1502:{\displaystyle f(L)=\bigcup _{s\in L}f(s)}
1292:
1269:
4819:
3465:
3461:
2828:String projection may be promoted to the
2575:
5034:Comparison of regular-expression engines
4676:
3798:The empty string is always cancellable:
3177:, one may define the quotient subset as
2368:
1052:{\displaystyle \operatorname {Alph} (s)}
46:
4789:Hopcroft, Ullman (1979), Sect.3.2, p.62
4735:Hopcroft, Ullman (1979), Sect.3.2, p.60
3594:{\displaystyle \{S/m\ \vert \ m\in M\}}
2259:{\displaystyle L\subseteq f^{-1}(f(L))}
2201:{\displaystyle f(f^{-1}(L))\subseteq L}
1007:
35:, frequent use is made of a variety of
14:
5204:
4679:closure under arbitrary substitutions.
1821:, preserving the empty string and the
1718:
1519:are closed under string substitution.
1330:
4995:Zhu–Takaoka string matching algorithm
4843:
3627:
3374:
2322:{\displaystyle f(a)\neq \varepsilon }
1261:{\displaystyle \langle cacao\rangle }
4804:"Derivatives of Regular Expressions"
2492:
4960:Boyer–Moore string-search algorithm
2944:is the truncation of the character
2579:{\displaystyle \pi _{\Sigma }(s)\,}
1522:A simple example is the conversion
446:are languages, their concatenation
24:
3883:
3855:
2879:
2854:
2774:
2723:
2711:
2663:
2601:
2561:
2536:
2508:
2340:
2145:{\displaystyle f(f^{-1}(L))\neq L}
1693:(‹Go!›) = {‹G›} ⋅ {‹O›} ⋅ {} = {}.
75:. The concatenation of two string
25:
5233:
5049:Nondeterministic finite automaton
4990:Two-way string-matching algorithm
2432:({ ‹A›, ‹bb› }) = { ‹a› }, since
1684:(‹u2›) = {‹U›} ⋅ {ε} = {‹U›}, and
2823:projection in relational algebra
1790:is a string, for each character
622:{\displaystyle \{\varepsilon \}}
4792:
4783:
4403:The prefix closure operator is
3379:The right quotient of a subset
3371:, so can be the left quotient.
2360:An example string homomorphism
1727:(often referred to simply as a
1343:, and let Σ be its alphabet. A
1320:{\displaystyle D\cdot D\cdot D}
997:{\displaystyle D\cdot D\cdot D}
580:. Again, the concatenation dot
4965:Boyer–Moore–Horspool algorithm
4955:Apostolico–Giancarlo algorithm
4774:
4765:
4756:
4747:
4738:
4729:
4669:
4641:
4635:
4610:
4560:
4554:
4521:{\displaystyle s\sqsubseteq t}
4459:
4453:
4441:
4438:
4432:
4423:
4381:
4375:
4300:
4294:
4219:
4212:
4144:
4138:
4103:
4097:
4023:
4016:
3958:
3952:
3900:
3888:
3866:
3860:
3754:
3742:
3697:
3688:
3678:and is recursively defined as
3481:
3469:
3003:
2994:
2980:. If the string does not have
2890:
2884:
2865:
2859:
2734:
2728:
2674:
2668:
2612:
2606:
2572:
2566:
2310:
2304:
2253:
2250:
2244:
2238:
2189:
2186:
2180:
2164:
2133:
2130:
2124:
2108:
2074:
2068:
2050:
2044:
1978:
1972:
1954:
1948:
1865:
1859:
1751:
1745:
1496:
1490:
1465:
1459:
1230:is the alphabet of the string
1158:
1152:
1124:
1118:
1046:
1040:
804:
792:
786:
774:
600:is often omitted for brevity.
335:
314:
308:
284:
255:
243:
237:
225:
208:. Concatenation of strings is
13:
1:
4686:
2839:, its projection is given by
1601:map uppercase char to itself
4970:Knuth–Morris–Pratt algorithm
4897:Damerau–Levenshtein distance
4495:{\displaystyle \sqsubseteq }
4079:prefix closure of a language
3604:is finite. In the case that
2810:{\displaystyle \varepsilon }
68:{\displaystyle \varepsilon }
7:
5161:Compressed pattern matching
4887:Approximate string matching
4869:
4580:
3916:
1704:to languages, we have e.g.
10:
5238:
5166:Longest common subsequence
5077:Needleman–Wunsch algorithm
4947:String-searching algorithm
4659:{\displaystyle f(a)=\{s\}}
3398:{\displaystyle S\subset M}
3349:and an arbitrary language
3284:over the same alphabet as
3150:{\displaystyle S\subset M}
3131:Similarly, given a subset
1631:map digit to empty string
826:For example, abbreviating
5222:String (computer science)
5176:Sequential pattern mining
5143:
5090:
5057:
5024:
5016:Commentz-Walter algorithm
5004:Multiple string searching
5003:
4945:
4937:Wagner–Fischer algorithm
4877:
4597:String (computer science)
2450:For the latter language,
1904:inverse homomorphic image
1813:String homomorphisms are
1665:to strings, we have e.g.
5186:String rewriting systems
5171:Longest common substring
5082:Smith–Waterman algorithm
4907:Gestalt pattern matching
4603:
3331:and distinct characters
2830:projection of a language
1652:similar for other chars
465:{\displaystyle S\cdot T}
134:{\displaystyle s\cdot t}
5120:Generalized suffix tree
5044:Thompson's construction
3671:{\displaystyle s\div a}
2928:Right and left quotient
2542:{\displaystyle \Sigma }
2514:{\displaystyle \Sigma }
2385:(‹0›) = ε, but letting
2353:. Simple single-letter
2346:{\displaystyle \Sigma }
1291:is the alphabet of the
5072:Hirschberg's algorithm
4675:This follows from the
4660:
4567:
4522:
4496:
4466:
4394:
4350:
4237:
4068:
4067:{\displaystyle s\in L}
4039:
3907:
3827:
3789:
3672:
3618:finite state automaton
3595:
3537:
3419:
3399:
3241:
3171:
3151:
3122:
3082:
2974:
2918:
2811:
2788:
2650: the empty string
2580:
2543:
2515:
2347:
2323:
2282:
2260:
2202:
2152:, while one does have
2146:
2090:
2016:
1994:
1920:
1896:
1872:
1843:
1804:
1784:
1764:
1763:{\displaystyle f(a)=s}
1733:formal language theory
1517:context-free languages
1503:
1321:
1285:
1262:
1224:
1165:
1099:
1079:
1064:alphabet of a language
1053:
998:
966:
817:
755:
702:
646:
623:
594:
593:{\displaystyle \cdot }
574:
506:
486:
466:
440:
420:
393:
268:
202:
158:
135:
109:
89:
69:
33:formal language theory
4927:Levenshtein automaton
4917:Jaro–Winkler distance
4821:10.1145/321239.321249
4661:
4568:
4523:
4497:
4467:
4395:
4358:A language is called
4351:
4238:
4069:
4040:
3908:
3828:
3790:
3673:
3596:
3538:
3420:
3400:
3358:Brzozowski derivative
3242:
3172:
3152:
3123:
3083:
2975:
2919:
2812:
2789:
2581:
2544:
2516:
2348:
2324:
2283:
2261:
2203:
2147:
2091:
2017:
1995:
1921:
1897:
1873:
1844:
1805:
1785:
1765:
1697:For the extension of
1658:For the extension of
1504:
1322:
1286:
1263:
1225:
1174:For example, the set
1166:
1100:
1080:
1054:
999:
967:
818:
756:
703:
647:
624:
595:
575:
507:
487:
467:
441:
421:
394:
269:
203:
159:
136:
110:
90:
70:
47:Strings and languages
4975:Rabin–Karp algorithm
4932:Levenshtein distance
4800:Janusz A. Brzozowski
4629:
4532:
4506:
4486:
4414:
4366:
4253:
4088:
4052:
3936:
3923:prefixes of a string
3847:
3805:
3685:
3656:
3553:
3447:
3427:equivalence relation
3409:
3383:
3367:is represented by a
3184:
3161:
3135:
3098:
2991:
2956:
2846:
2801:
2593:
2553:
2533:
2521:is an alphabet, the
2505:
2355:substitution ciphers
2337:
2298:
2272:
2216:
2158:
2102:
2028:
2006:
1932:
1910:
1886:
1871:{\displaystyle f(L)}
1853:
1833:
1829:. Given a language
1827:string concatenation
1794:
1774:
1739:
1453:
1299:
1275:
1234:
1178:
1109:
1089:
1069:
1031:
1014:alphabet of a string
1008:Alphabet of a string
976:
830:
765:
712:
656:
645:{\displaystyle \{\}}
633:
607:
584:
516:
496:
492:and any string from
476:
450:
430:
410:
281:
216:
168:
145:
119:
99:
79:
59:
41:computer programming
5130:Ternary search tree
2973:{\displaystyle s/a}
2549:. It is written as
2485:-encoded string to
2464:({ ‹A›, ‹bb› })) =
2423:(‹ßs›) = ‹SSS›, and
1725:string homomorphism
1719:String homomorphism
1345:string substitution
1331:String substitution
5217:Relational algebra
5059:Sequence alignment
5026:Regular expression
4656:
4563:
4518:
4492:
4462:
4390:
4346:
4286:
4233:
4124:
4064:
4035:
3996:
3925:is the set of all
3903:
3823:
3785:
3780:
3767:
3727:
3668:
3634:right cancellation
3628:Right cancellation
3591:
3533:
3433:syntactic relation
3415:
3395:
3375:Syntactic relation
3369:regular expression
3237:
3167:
3147:
3118:
3078:
3073:
3060:
3035:
2970:
2914:
2807:
2784:
2779:
2766:
2747:
2703:
2684:
2652:
2636:
2576:
2539:
2511:
2378:(‹a›) = ‹A›, ...,
2343:
2319:
2278:
2256:
2198:
2142:
2086:
2012:
1990:
1916:
1892:
1868:
1839:
1800:
1780:
1760:
1538:mapped to language
1499:
1486:
1317:
1281:
1258:
1220:
1161:
1145:
1095:
1075:
1049:
994:
962:
813:
751:
698:
642:
619:
590:
570:
502:
482:
462:
436:
416:
389:
264:
198:
157:{\displaystyle st}
154:
131:
105:
85:
65:
5199:
5198:
5191:String operations
4708:978-0-201-02988-8
4285:
4166:
4160:
4109:
3995:
3978:
3972:
3766:
3726:
3622:syntactic monoids
3578:
3572:
3504:
3498:
3440:. It is given by
3418:{\displaystyle M}
3270:of the languages
3221:
3215:
3170:{\displaystyle M}
3059:
3034:
2901:
2895:
2765:
2746:
2702:
2683:
2651:
2635:
2523:string projection
2501:is a string, and
2493:String projection
2281:{\displaystyle L}
2268:for any language
2015:{\displaystyle L}
1919:{\displaystyle s}
1895:{\displaystyle L}
1880:homomorphic image
1842:{\displaystyle L}
1803:{\displaystyle a}
1783:{\displaystyle s}
1656:
1655:
1513:Regular languages
1471:
1284:{\displaystyle D}
1130:
1098:{\displaystyle S}
1078:{\displaystyle S}
1020:is a string, its
505:{\displaystyle T}
485:{\displaystyle S}
439:{\displaystyle T}
419:{\displaystyle S}
108:{\displaystyle t}
88:{\displaystyle s}
31:, in the area of
16:(Redirected from
5229:
5212:Formal languages
5156:Pattern matching
5110:Suffix automaton
4912:Hamming distance
4864:
4857:
4850:
4841:
4840:
4834:
4833:
4823:
4796:
4790:
4787:
4781:
4778:
4772:
4769:
4763:
4760:
4754:
4751:
4745:
4742:
4736:
4733:
4722:(See chapter 3.)
4720:
4700:
4680:
4673:
4667:
4665:
4663:
4662:
4657:
4623:
4617:
4614:
4572:
4570:
4569:
4564:
4550:
4549:
4527:
4525:
4524:
4519:
4501:
4499:
4498:
4493:
4471:
4469:
4468:
4463:
4399:
4397:
4396:
4391:
4355:
4353:
4352:
4347:
4345:
4341:
4287:
4284: then
4283:
4280:
4276:
4242:
4240:
4239:
4234:
4232:
4228:
4227:
4226:
4164:
4158:
4134:
4133:
4123:
4073:
4071:
4070:
4065:
4044:
4042:
4041:
4036:
4031:
4030:
3997:
3993:
3976:
3970:
3948:
3947:
3912:
3910:
3909:
3904:
3887:
3886:
3859:
3858:
3832:
3830:
3829:
3824:
3794:
3792:
3791:
3786:
3784:
3783:
3768:
3764:
3728:
3724:
3677:
3675:
3674:
3669:
3614:regular language
3600:
3598:
3597:
3592:
3576:
3570:
3566:
3542:
3540:
3539:
3534:
3526:
3512:
3502:
3496:
3459:
3458:
3424:
3422:
3421:
3416:
3404:
3402:
3401:
3396:
3326:
3246:
3244:
3243:
3238:
3219:
3213:
3194:
3176:
3174:
3173:
3168:
3156:
3154:
3153:
3148:
3127:
3125:
3124:
3119:
3108:
3087:
3085:
3084:
3079:
3077:
3076:
3061:
3057:
3036:
3032:
3010:
2979:
2977:
2976:
2971:
2966:
2923:
2921:
2920:
2915:
2899:
2893:
2883:
2882:
2858:
2857:
2816:
2814:
2813:
2808:
2793:
2791:
2790:
2785:
2783:
2782:
2767:
2763:
2748:
2744:
2727:
2726:
2704:
2700:
2685:
2681:
2667:
2666:
2653:
2649:
2637:
2633:
2605:
2604:
2585:
2583:
2582:
2577:
2565:
2564:
2548:
2546:
2545:
2540:
2520:
2518:
2517:
2512:
2352:
2350:
2349:
2344:
2333:in the alphabet
2328:
2326:
2325:
2320:
2287:
2285:
2284:
2279:
2265:
2263:
2262:
2257:
2237:
2236:
2207:
2205:
2204:
2199:
2179:
2178:
2151:
2149:
2148:
2143:
2123:
2122:
2095:
2093:
2092:
2087:
2043:
2042:
2021:
2019:
2018:
2013:
1999:
1997:
1996:
1991:
1947:
1946:
1925:
1923:
1922:
1917:
1901:
1899:
1898:
1893:
1877:
1875:
1874:
1869:
1848:
1846:
1845:
1840:
1823:binary operation
1815:monoid morphisms
1809:
1807:
1806:
1801:
1789:
1787:
1786:
1781:
1769:
1767:
1766:
1761:
1532:
1531:
1508:
1506:
1505:
1500:
1485:
1326:
1324:
1323:
1318:
1290:
1288:
1287:
1282:
1267:
1265:
1264:
1259:
1229:
1227:
1226:
1221:
1170:
1168:
1167:
1162:
1144:
1104:
1102:
1101:
1096:
1084:
1082:
1081:
1076:
1058:
1056:
1055:
1050:
1003:
1001:
1000:
995:
971:
969:
968:
963:
822:
820:
819:
814:
760:
758:
757:
752:
707:
705:
704:
699:
651:
649:
648:
643:
628:
626:
625:
620:
599:
597:
596:
591:
579:
577:
576:
571:
511:
509:
508:
503:
491:
489:
488:
483:
471:
469:
468:
463:
445:
443:
442:
437:
425:
423:
422:
417:
398:
396:
395:
390:
273:
271:
270:
265:
207:
205:
204:
199:
163:
161:
160:
155:
141:, or shorter by
140:
138:
137:
132:
114:
112:
111:
106:
94:
92:
91:
86:
74:
72:
71:
66:
37:string functions
29:computer science
21:
5237:
5236:
5232:
5231:
5230:
5228:
5227:
5226:
5202:
5201:
5200:
5195:
5139:
5086:
5053:
5039:Regular grammar
5020:
4999:
4980:Raita algorithm
4941:
4892:Bitap algorithm
4873:
4868:
4838:
4837:
4797:
4793:
4788:
4784:
4779:
4775:
4770:
4766:
4761:
4757:
4752:
4748:
4743:
4739:
4734:
4730:
4709:
4689:
4684:
4683:
4677:above-mentioned
4674:
4670:
4630:
4627:
4626:
4624:
4620:
4615:
4611:
4606:
4583:
4545:
4541:
4533:
4530:
4529:
4528:if and only if
4507:
4504:
4503:
4487:
4484:
4483:
4481:binary relation
4477:prefix relation
4415:
4412:
4411:
4367:
4364:
4363:
4310:
4306:
4281:
4266:
4262:
4254:
4251:
4250:
4249:
4222:
4218:
4154:
4150:
4129:
4125:
4113:
4089:
4086:
4085:
4053:
4050:
4049:
4026:
4022:
3994: for
3991:
3943:
3939:
3937:
3934:
3933:
3919:
3882:
3878:
3854:
3850:
3848:
3845:
3844:
3806:
3803:
3802:
3779:
3778:
3762:
3760:
3739:
3738:
3722:
3720:
3710:
3709:
3686:
3683:
3682:
3657:
3654:
3653:
3636:of a character
3630:
3562:
3554:
3551:
3550:
3522:
3508:
3454:
3450:
3448:
3445:
3444:
3410:
3407:
3406:
3384:
3381:
3380:
3377:
3366:
3355:
3348:
3324:
3313:
3298:
3291:
3285:
3283:
3276:
3269:
3262:
3190:
3185:
3182:
3181:
3162:
3159:
3158:
3136:
3133:
3132:
3104:
3099:
3096:
3095:
3072:
3071:
3055:
3053:
3047:
3046:
3030:
3028:
3018:
3017:
3006:
2992:
2989:
2988:
2962:
2957:
2954:
2953:
2936:of a character
2930:
2878:
2874:
2853:
2849:
2847:
2844:
2843:
2834:formal language
2802:
2799:
2798:
2778:
2777:
2764: and
2761:
2742:
2740:
2722:
2718:
2715:
2714:
2701: and
2698:
2679:
2677:
2662:
2658:
2655:
2654:
2647:
2631:
2629:
2619:
2618:
2600:
2596:
2594:
2591:
2590:
2560:
2556:
2554:
2551:
2550:
2534:
2531:
2530:
2506:
2503:
2502:
2495:
2477:
2470:
2463:
2456:
2445:
2438:
2431:
2422:
2415:
2408:
2401:
2391:
2384:
2377:
2366:
2338:
2335:
2334:
2299:
2296:
2295:
2273:
2270:
2269:
2229:
2225:
2217:
2214:
2213:
2171:
2167:
2159:
2156:
2155:
2115:
2111:
2103:
2100:
2099:
2035:
2031:
2029:
2026:
2025:
2007:
2004:
2003:
1939:
1935:
1933:
1930:
1929:
1911:
1908:
1907:
1887:
1884:
1883:
1854:
1851:
1850:
1834:
1831:
1830:
1795:
1792:
1791:
1775:
1772:
1771:
1740:
1737:
1736:
1721:
1713:
1703:
1692:
1683:
1674:
1664:
1556:
1528:
1475:
1454:
1451:
1450:
1384:
1375:
1333:
1300:
1297:
1296:
1276:
1273:
1272:
1235:
1232:
1231:
1179:
1176:
1175:
1134:
1110:
1107:
1106:
1090:
1087:
1086:
1070:
1067:
1066:
1032:
1029:
1028:
1010:
977:
974:
973:
831:
828:
827:
766:
763:
762:
713:
710:
709:
657:
654:
653:
634:
631:
630:
608:
605:
604:
585:
582:
581:
517:
514:
513:
497:
494:
493:
477:
474:
473:
451:
448:
447:
431:
428:
427:
411:
408:
407:
282:
279:
278:
217:
214:
213:
169:
166:
165:
146:
143:
142:
120:
117:
116:
100:
97:
96:
80:
77:
76:
60:
57:
56:
49:
23:
22:
15:
12:
11:
5:
5235:
5225:
5224:
5219:
5214:
5197:
5196:
5194:
5193:
5188:
5183:
5178:
5173:
5168:
5163:
5158:
5153:
5147:
5145:
5141:
5140:
5138:
5137:
5132:
5127:
5122:
5117:
5112:
5107:
5102:
5096:
5094:
5092:Data structure
5088:
5087:
5085:
5084:
5079:
5074:
5069:
5063:
5061:
5055:
5054:
5052:
5051:
5046:
5041:
5036:
5030:
5028:
5022:
5021:
5019:
5018:
5013:
5007:
5005:
5001:
5000:
4998:
4997:
4992:
4987:
4985:Trigram search
4982:
4977:
4972:
4967:
4962:
4957:
4951:
4949:
4943:
4942:
4940:
4939:
4934:
4929:
4924:
4919:
4914:
4909:
4904:
4899:
4894:
4889:
4883:
4881:
4875:
4874:
4867:
4866:
4859:
4852:
4844:
4836:
4835:
4814:(4): 481–494.
4791:
4782:
4773:
4764:
4755:
4746:
4737:
4727:
4726:
4725:
4724:
4707:
4688:
4685:
4682:
4681:
4668:
4655:
4652:
4649:
4646:
4643:
4640:
4637:
4634:
4618:
4608:
4607:
4605:
4602:
4601:
4600:
4594:
4589:
4582:
4579:
4562:
4559:
4556:
4553:
4548:
4544:
4540:
4537:
4517:
4514:
4511:
4491:
4473:
4472:
4461:
4458:
4455:
4452:
4449:
4446:
4443:
4440:
4437:
4434:
4431:
4428:
4425:
4422:
4419:
4389:
4386:
4383:
4380:
4377:
4374:
4371:
4344:
4340:
4337:
4334:
4331:
4328:
4325:
4322:
4319:
4316:
4313:
4309:
4305:
4302:
4299:
4296:
4293:
4290:
4279:
4275:
4272:
4269:
4265:
4261:
4258:
4244:
4243:
4231:
4225:
4221:
4217:
4214:
4211:
4208:
4205:
4202:
4199:
4196:
4193:
4190:
4187:
4184:
4181:
4178:
4175:
4172:
4169:
4163:
4157:
4153:
4149:
4146:
4143:
4140:
4137:
4132:
4128:
4122:
4119:
4116:
4112:
4108:
4105:
4102:
4099:
4096:
4093:
4063:
4060:
4057:
4046:
4045:
4034:
4029:
4025:
4021:
4018:
4015:
4012:
4009:
4006:
4003:
4000:
3990:
3987:
3984:
3981:
3975:
3969:
3966:
3963:
3960:
3957:
3954:
3951:
3946:
3942:
3918:
3915:
3914:
3913:
3902:
3899:
3896:
3893:
3890:
3885:
3881:
3877:
3874:
3871:
3868:
3865:
3862:
3857:
3853:
3834:
3833:
3822:
3819:
3816:
3813:
3810:
3796:
3795:
3782:
3777:
3774:
3771:
3761:
3759:
3756:
3753:
3750:
3747:
3744:
3741:
3740:
3737:
3734:
3731:
3721:
3719:
3716:
3715:
3713:
3708:
3705:
3702:
3699:
3696:
3693:
3690:
3667:
3664:
3661:
3648:in the string
3640:from a string
3629:
3626:
3602:
3601:
3590:
3587:
3584:
3581:
3575:
3569:
3565:
3561:
3558:
3544:
3543:
3532:
3529:
3525:
3521:
3518:
3515:
3511:
3507:
3501:
3495:
3492:
3489:
3486:
3483:
3480:
3477:
3474:
3471:
3468:
3464:
3457:
3453:
3414:
3394:
3391:
3388:
3376:
3373:
3364:
3353:
3346:
3322:
3311:
3296:
3289:
3281:
3274:
3267:
3260:
3251:Left quotients
3248:
3247:
3236:
3233:
3230:
3227:
3224:
3218:
3212:
3209:
3206:
3203:
3200:
3197:
3193:
3189:
3166:
3146:
3143:
3140:
3129:
3128:
3117:
3114:
3111:
3107:
3103:
3089:
3088:
3075:
3070:
3067:
3064:
3054:
3052:
3049:
3048:
3045:
3042:
3039:
3029:
3027:
3024:
3023:
3021:
3016:
3013:
3009:
3005:
3002:
2999:
2996:
2969:
2965:
2961:
2948:in the string
2940:from a string
2934:right quotient
2929:
2926:
2925:
2924:
2913:
2910:
2907:
2904:
2898:
2892:
2889:
2886:
2881:
2877:
2873:
2870:
2867:
2864:
2861:
2856:
2852:
2806:
2795:
2794:
2781:
2776:
2773:
2770:
2760:
2757:
2754:
2751:
2741:
2739:
2736:
2733:
2730:
2725:
2721:
2717:
2716:
2713:
2710:
2707:
2697:
2694:
2691:
2688:
2678:
2676:
2673:
2670:
2665:
2661:
2657:
2656:
2646:
2643:
2640:
2630:
2628:
2625:
2624:
2622:
2617:
2614:
2611:
2608:
2603:
2599:
2574:
2571:
2568:
2563:
2559:
2538:
2510:
2494:
2491:
2475:
2468:
2461:
2454:
2448:
2447:
2443:
2436:
2429:
2424:
2420:
2413:
2406:
2399:
2389:
2382:
2375:
2371:substitution:
2364:
2342:
2318:
2315:
2312:
2309:
2306:
2303:
2277:
2255:
2252:
2249:
2246:
2243:
2240:
2235:
2232:
2228:
2224:
2221:
2197:
2194:
2191:
2188:
2185:
2182:
2177:
2174:
2170:
2166:
2163:
2141:
2138:
2135:
2132:
2129:
2126:
2121:
2118:
2114:
2110:
2107:
2085:
2082:
2079:
2076:
2073:
2070:
2067:
2064:
2061:
2058:
2055:
2052:
2049:
2046:
2041:
2038:
2034:
2022:is defined as
2011:
1989:
1986:
1983:
1980:
1977:
1974:
1971:
1968:
1965:
1962:
1959:
1956:
1953:
1950:
1945:
1942:
1938:
1926:is defined as
1915:
1891:
1878:is called the
1867:
1864:
1861:
1858:
1838:
1799:
1779:
1759:
1756:
1753:
1750:
1747:
1744:
1720:
1717:
1716:
1715:
1711:
1701:
1695:
1694:
1690:
1685:
1681:
1676:
1672:
1662:
1654:
1653:
1650:
1648:
1644:
1643:
1640:
1637:
1633:
1632:
1629:
1626:
1622:
1621:
1618:
1611:
1603:
1602:
1599:
1592:
1584:
1583:
1580:
1573:
1565:
1564:
1562:
1554:
1549:
1543:
1542:
1539:
1536:
1526:
1510:
1509:
1498:
1495:
1492:
1489:
1484:
1481:
1478:
1474:
1470:
1467:
1464:
1461:
1458:
1442:and character
1432:
1431:
1397:
1396:
1380:
1371:
1332:
1329:
1316:
1313:
1310:
1307:
1304:
1280:
1257:
1254:
1251:
1248:
1245:
1242:
1239:
1219:
1216:
1213:
1210:
1207:
1204:
1201:
1198:
1195:
1192:
1189:
1186:
1183:
1160:
1157:
1154:
1151:
1148:
1143:
1140:
1137:
1133:
1129:
1126:
1123:
1120:
1117:
1114:
1094:
1074:
1060:
1059:
1048:
1045:
1042:
1039:
1036:
1024:is denoted by
1009:
1006:
993:
990:
987:
984:
981:
961:
958:
955:
952:
949:
946:
943:
940:
937:
934:
931:
928:
925:
922:
919:
916:
913:
910:
907:
904:
901:
898:
895:
892:
889:
886:
883:
880:
877:
874:
871:
868:
865:
862:
859:
856:
853:
850:
847:
844:
841:
838:
835:
812:
809:
806:
803:
800:
797:
794:
791:
788:
785:
782:
779:
776:
773:
770:
750:
747:
744:
741:
738:
735:
732:
729:
726:
723:
720:
717:
697:
694:
691:
688:
685:
682:
679:
676:
673:
670:
667:
664:
661:
641:
638:
618:
615:
612:
589:
569:
566:
563:
560:
557:
554:
551:
548:
545:
542:
539:
536:
533:
530:
527:
524:
521:
501:
481:
461:
458:
455:
435:
415:
388:
385:
382:
379:
376:
373:
370:
367:
364:
361:
358:
355:
352:
349:
346:
343:
340:
337:
334:
331:
328:
325:
322:
319:
316:
313:
310:
307:
304:
301:
298:
295:
292:
289:
286:
263:
260:
257:
254:
251:
248:
245:
242:
239:
236:
233:
230:
227:
224:
221:
197:
194:
191:
188:
185:
182:
179:
176:
173:
153:
150:
130:
127:
124:
115:is denoted by
104:
84:
64:
55:is denoted by
48:
45:
9:
6:
4:
3:
2:
5234:
5223:
5220:
5218:
5215:
5213:
5210:
5209:
5207:
5192:
5189:
5187:
5184:
5182:
5179:
5177:
5174:
5172:
5169:
5167:
5164:
5162:
5159:
5157:
5154:
5152:
5149:
5148:
5146:
5142:
5136:
5133:
5131:
5128:
5126:
5123:
5121:
5118:
5116:
5113:
5111:
5108:
5106:
5103:
5101:
5098:
5097:
5095:
5093:
5089:
5083:
5080:
5078:
5075:
5073:
5070:
5068:
5065:
5064:
5062:
5060:
5056:
5050:
5047:
5045:
5042:
5040:
5037:
5035:
5032:
5031:
5029:
5027:
5023:
5017:
5014:
5012:
5009:
5008:
5006:
5002:
4996:
4993:
4991:
4988:
4986:
4983:
4981:
4978:
4976:
4973:
4971:
4968:
4966:
4963:
4961:
4958:
4956:
4953:
4952:
4950:
4948:
4944:
4938:
4935:
4933:
4930:
4928:
4925:
4923:
4920:
4918:
4915:
4913:
4910:
4908:
4905:
4903:
4902:Edit distance
4900:
4898:
4895:
4893:
4890:
4888:
4885:
4884:
4882:
4880:
4879:String metric
4876:
4872:
4865:
4860:
4858:
4853:
4851:
4846:
4845:
4842:
4831:
4827:
4822:
4817:
4813:
4809:
4805:
4801:
4795:
4786:
4777:
4768:
4759:
4750:
4741:
4732:
4728:
4723:
4718:
4714:
4710:
4704:
4699:
4698:
4691:
4690:
4678:
4672:
4650:
4644:
4638:
4632:
4622:
4613:
4609:
4598:
4595:
4593:
4590:
4588:
4585:
4584:
4578:
4576:
4557:
4551:
4546:
4542:
4538:
4535:
4515:
4512:
4509:
4489:
4482:
4478:
4456:
4450:
4447:
4444:
4435:
4429:
4426:
4420:
4417:
4410:
4409:
4408:
4406:
4401:
4387:
4384:
4378:
4372:
4369:
4361:
4360:prefix closed
4356:
4342:
4338:
4335:
4332:
4329:
4326:
4323:
4320:
4317:
4314:
4311:
4307:
4303:
4297:
4291:
4288:
4277:
4273:
4270:
4267:
4263:
4259:
4256:
4248:
4229:
4223:
4215:
4209:
4206:
4203:
4200:
4197:
4194:
4191:
4188:
4185:
4182:
4179:
4176:
4173:
4170:
4167:
4155:
4151:
4147:
4141:
4135:
4130:
4126:
4120:
4117:
4114:
4110:
4106:
4100:
4094:
4091:
4084:
4083:
4082:
4080:
4075:
4061:
4058:
4055:
4027:
4019:
4013:
4010:
4007:
4004:
4001:
3998:
3988:
3985:
3982:
3979:
3967:
3961:
3955:
3949:
3944:
3940:
3932:
3931:
3930:
3928:
3924:
3897:
3894:
3891:
3879:
3875:
3872:
3869:
3863:
3851:
3843:
3842:
3841:
3839:
3820:
3817:
3814:
3811:
3808:
3801:
3800:
3799:
3775:
3772:
3769:
3757:
3751:
3748:
3745:
3735:
3732:
3729:
3717:
3711:
3706:
3703:
3700:
3694:
3691:
3681:
3680:
3679:
3665:
3662:
3659:
3651:
3647:
3643:
3639:
3635:
3625:
3623:
3619:
3615:
3611:
3607:
3585:
3582:
3579:
3567:
3563:
3559:
3549:
3548:
3547:
3527:
3523:
3519:
3516:
3513:
3509:
3505:
3493:
3490:
3487:
3484:
3478:
3475:
3472:
3462:
3455:
3451:
3443:
3442:
3441:
3439:
3435:
3434:
3429:, called the
3428:
3412:
3392:
3389:
3386:
3372:
3370:
3363:
3359:
3352:
3345:
3340:
3338:
3334:
3330:
3321:
3317:
3310:
3306:
3302:
3295:
3288:
3280:
3273:
3266:
3259:
3254:
3252:
3231:
3228:
3225:
3222:
3210:
3207:
3204:
3198:
3195:
3191:
3187:
3180:
3179:
3178:
3164:
3144:
3141:
3138:
3115:
3112:
3109:
3105:
3101:
3094:
3093:
3092:
3068:
3065:
3062:
3050:
3043:
3040:
3037:
3025:
3019:
3014:
3011:
3007:
3000:
2997:
2987:
2986:
2985:
2983:
2967:
2963:
2959:
2951:
2947:
2943:
2939:
2935:
2908:
2905:
2902:
2887:
2875:
2868:
2862:
2850:
2842:
2841:
2840:
2838:
2835:
2831:
2826:
2824:
2820:
2804:
2771:
2768:
2758:
2755:
2752:
2749:
2737:
2731:
2719:
2708:
2705:
2695:
2692:
2689:
2686:
2671:
2659:
2644:
2641:
2638:
2626:
2620:
2615:
2609:
2597:
2589:
2588:
2587:
2569:
2557:
2528:
2524:
2500:
2490:
2488:
2484:
2479:
2474:
2467:
2460:
2453:
2442:
2435:
2428:
2425:
2419:
2412:
2405:
2398:
2395:
2394:
2393:
2388:
2381:
2374:
2370:
2363:
2358:
2356:
2332:
2316:
2313:
2307:
2301:
2292:
2289:
2275:
2266:
2247:
2241:
2233:
2230:
2226:
2222:
2219:
2211:
2208:
2195:
2192:
2183:
2175:
2172:
2168:
2161:
2153:
2139:
2136:
2127:
2119:
2116:
2112:
2105:
2096:
2080:
2077:
2071:
2065:
2062:
2059:
2053:
2047:
2039:
2036:
2032:
2023:
2009:
2000:
1984:
1981:
1975:
1969:
1966:
1963:
1957:
1951:
1943:
1940:
1936:
1927:
1913:
1905:
1889:
1881:
1862:
1856:
1836:
1828:
1824:
1820:
1816:
1811:
1797:
1777:
1757:
1754:
1748:
1742:
1734:
1730:
1726:
1710:
1707:
1706:
1705:
1700:
1689:
1686:
1680:
1677:
1671:
1668:
1667:
1666:
1661:
1651:
1649:
1646:
1645:
1641:
1638:
1635:
1634:
1630:
1627:
1624:
1623:
1619:
1616:
1612:
1609:
1605:
1604:
1600:
1597:
1593:
1590:
1586:
1585:
1581:
1578:
1574:
1571:
1567:
1566:
1563:
1560:
1553:
1550:
1548:
1545:
1544:
1540:
1537:
1534:
1533:
1530:
1525:
1520:
1518:
1514:
1493:
1487:
1482:
1479:
1476:
1472:
1468:
1462:
1456:
1449:
1448:
1447:
1445:
1441:
1437:
1429:
1425:
1421:
1417:
1413:
1409:
1406:
1405:
1404:
1402:
1394:
1391:
1390:
1389:
1387:
1383:
1379:
1374:
1370:
1366:
1362:
1359:∈ Σ, one has
1358:
1354:
1351:is a mapping
1350:
1346:
1342:
1338:
1328:
1314:
1311:
1308:
1305:
1302:
1294:
1278:
1271:
1252:
1249:
1246:
1243:
1240:
1211:
1205:
1199:
1193:
1187:
1172:
1155:
1149:
1146:
1141:
1138:
1135:
1131:
1127:
1121:
1115:
1112:
1092:
1072:
1065:
1043:
1037:
1034:
1027:
1026:
1025:
1023:
1019:
1015:
1005:
991:
988:
985:
982:
979:
953:
947:
941:
935:
929:
923:
917:
911:
905:
899:
893:
887:
881:
875:
869:
863:
857:
851:
845:
836:
833:
824:
810:
807:
801:
798:
795:
789:
783:
780:
777:
771:
768:
748:
745:
736:
727:
718:
715:
695:
692:
686:
680:
677:
674:
668:
662:
659:
613:
603:The language
601:
587:
564:
561:
558:
555:
552:
549:
546:
543:
540:
537:
534:
528:
525:
522:
519:
499:
479:
459:
456:
453:
433:
413:
405:
400:
383:
380:
377:
374:
368:
362:
359:
353:
347:
344:
338:
329:
326:
320:
317:
311:
302:
296:
290:
277:For example,
275:
261:
258:
252:
249:
246:
240:
234:
231:
228:
222:
219:
211:
195:
192:
189:
186:
183:
180:
177:
174:
171:
151:
148:
128:
125:
122:
102:
82:
62:
54:
44:
42:
38:
34:
30:
19:
18:Prefix closed
5190:
5105:Suffix array
5011:Aho–Corasick
4922:Lee distance
4811:
4807:
4794:
4785:
4776:
4767:
4758:
4749:
4740:
4731:
4721:
4696:
4671:
4621:
4612:
4592:Levi's lemma
4575:prefix order
4476:
4474:
4402:
4359:
4357:
4246:
4245:
4078:
4076:
4047:
3922:
3920:
3835:
3797:
3649:
3645:
3641:
3637:
3633:
3631:
3609:
3605:
3603:
3545:
3437:
3430:
3405:of a monoid
3378:
3361:
3356:is known as
3350:
3343:
3341:
3336:
3332:
3328:
3319:
3315:
3308:
3304:
3300:
3293:
3286:
3278:
3271:
3264:
3257:
3255:
3250:
3249:
3157:of a monoid
3130:
3090:
2981:
2949:
2945:
2941:
2937:
2933:
2931:
2836:
2829:
2827:
2819:empty string
2817:denotes the
2796:
2526:
2522:
2498:
2496:
2480:
2472:
2465:
2458:
2451:
2449:
2440:
2433:
2426:
2417:
2410:
2403:
2396:
2386:
2379:
2372:
2361:
2359:
2330:
2293:
2290:
2267:
2212:
2209:
2154:
2098:In general,
2097:
2024:
2001:
1928:
1906:of a string
1903:
1879:
1812:
1729:homomorphism
1724:
1722:
1708:
1698:
1696:
1687:
1678:
1669:
1659:
1657:
1614:
1607:
1595:
1588:
1576:
1569:
1558:
1551:
1546:
1523:
1521:
1511:
1443:
1439:
1435:
1433:
1427:
1423:
1419:
1415:
1411:
1407:
1401:empty string
1398:
1392:
1381:
1377:
1372:
1368:
1364:
1360:
1356:
1352:
1349:substitution
1348:
1347:or simply a
1344:
1336:
1334:
1173:
1105:, formally:
1063:
1061:
1017:
1013:
1011:
825:
602:
401:
276:
53:empty string
50:
26:
5115:Suffix tree
3425:defines an
1819:free monoid
1434:for string
512:, formally
210:associative
5206:Categories
4717:0426.68001
4687:References
4502:such that
4405:idempotent
3612:is then a
2832:. Given a
2409:(‹sss›) =
1849:, the set
1268:, and the
4552:
4539:∈
4513:⊑
4490:⊑
4451:
4430:
4421:
4373:
4312:ε
4292:
4224:∗
4210:
4204:∈
4186:∈
4136:
4118:∈
4111:⋃
4095:
4059:∈
4028:∗
4014:
4008:∈
3950:
3895:÷
3884:Σ
3880:π
3870:÷
3856:Σ
3852:π
3821:ε
3812:÷
3809:ε
3773:≠
3749:÷
3701:÷
3663:÷
3583:∈
3491:×
3485:∈
3452:∼
3390:⊂
3229:∈
3208:∈
3142:⊂
3116:ε
3102:ε
3066:≠
3051:ε
2906:∈
2880:Σ
2876:π
2855:Σ
2851:π
2805:ε
2775:Σ
2772:∈
2724:Σ
2720:π
2712:Σ
2709:∉
2664:Σ
2660:π
2645:ε
2627:ε
2602:Σ
2598:π
2562:Σ
2558:π
2537:Σ
2509:Σ
2416:(‹sß›) =
2341:Σ
2317:ε
2314:≠
2231:−
2223:⊆
2193:⊆
2173:−
2137:≠
2117:−
2078:∈
2063:∣
2037:−
1967:∣
1941:−
1535:character
1480:∈
1473:⋃
1312:⋅
1306:⋅
1295:language
1256:⟩
1238:⟨
1215:⟩
1209:⟨
1203:⟩
1197:⟨
1191:⟩
1185:⟨
1150:
1139:∈
1132:⋃
1116:
1038:
989:⋅
983:⋅
957:⟩
951:⟨
945:⟩
939:⟨
933:⟩
927:⟨
921:⟩
915:⟨
909:⟩
903:⟨
897:⟩
891:⟨
885:⟩
879:⟨
873:⟩
867:⟨
861:⟩
855:⟨
849:⟩
843:⟨
808:⋅
799:⋅
781:⋅
772:⋅
746:⋅
719:⋅
693:⋅
687:ε
669:ε
663:⋅
614:ε
588:⋅
562:∈
556:∧
550:∈
544:∣
538:⋅
523:⋅
457:⋅
387:⟩
372:⟨
366:⟩
357:⟨
354:⋅
351:⟩
342:⟨
333:⟩
324:⟨
321:⋅
318:ε
312:⋅
306:⟩
300:⟨
297:⋅
294:⟩
288:⟨
259:⋅
250:⋅
232:⋅
223:⋅
193:⋅
190:ε
178:ε
175:⋅
126:⋅
63:ε
4830:14126942
4802:(1964).
4581:See also
4247:Example:
3927:prefixes
3917:Prefixes
3765:if
3725:if
3058:if
3033:if
2745:if
2682:if
2634:if
2329:for all
1770:, where
1399:for the
1341:language
1022:alphabet
404:language
5181:Sorting
5151:Parsing
4871:Strings
3838:commute
1817:on the
1541:remark
1403:ε, and
4828:
4715:
4705:
4165:
4159:
4048:where
3977:
3971:
3577:
3571:
3503:
3497:
3431:right
3220:
3214:
2900:
2894:
2483:EBCDIC
1902:. The
1376:where
5144:Other
5100:DAFSA
5067:BLAST
4826:S2CID
4808:J ACM
4604:Notes
4479:is a
3360:; if
2797:Here
2487:ASCII
2369:above
1628:{ ε }
1395:(ε)=ε
1339:be a
1293:above
1270:above
5135:Trie
5125:Rope
4703:ISBN
4543:Pref
4475:The
4448:Pref
4427:Pref
4418:Pref
4370:Pref
4289:Pref
4207:Alph
4127:Pref
4092:Pref
4077:The
4011:Alph
3941:Pref
3921:The
3632:The
3299:= {
3277:and
2932:The
2210:and
1335:Let
1147:Alph
1113:Alph
1062:The
1035:Alph
1012:The
426:and
95:and
4816:doi
4713:Zbl
4362:if
4081:is
3436:of
3303:| ∃
2525:of
2497:If
1882:of
1825:of
1731:in
1647:...
1639:{ }
1636:‹!›
1625:‹0›
1617:› }
1613:{ ‹
1598:› }
1594:{ ‹
1579:› }
1575:{ ‹
1385:⊆ Δ
27:In
5208::
4824:.
4812:11
4810:.
4806:.
4711:.
4577:.
4407::
4400:.
4074:.
3840::
3624:.
3335:,
3316:st
3314:.
2825:.
2489:.
2476:uc
2469:uc
2462:uc
2455:uc
2444:uc
2437:uc
2430:uc
2421:uc
2414:uc
2407:uc
2400:uc
2390:uc
2383:uc
2376:uc
2365:uc
2288:.
1810:.
1723:A
1712:uc
1702:uc
1691:uc
1682:uc
1673:uc
1663:uc
1615:SS
1555:uc
1527:uc
1438:∈
1414:)=
1412:sa
1367:)=
1171:.
823:.
402:A
399:.
274:.
212::
4863:e
4856:t
4849:v
4832:.
4818::
4719:.
4666:.
4654:}
4651:s
4648:{
4645:=
4642:)
4639:a
4636:(
4633:f
4561:)
4558:t
4555:(
4547:L
4536:s
4516:t
4510:s
4460:)
4457:L
4454:(
4445:=
4442:)
4439:)
4436:L
4433:(
4424:(
4388:L
4385:=
4382:)
4379:L
4376:(
4343:}
4339:c
4336:b
4333:a
4330:,
4327:b
4324:a
4321:,
4318:a
4315:,
4308:{
4304:=
4301:)
4298:L
4295:(
4278:}
4274:c
4271:b
4268:a
4264:{
4260:=
4257:L
4230:}
4220:)
4216:L
4213:(
4201:u
4198:,
4195:t
4192:;
4189:L
4183:s
4180:;
4177:u
4174:t
4171:=
4168:s
4162:|
4156:t
4152:{
4148:=
4145:)
4142:s
4139:(
4131:L
4121:L
4115:s
4107:=
4104:)
4101:L
4098:(
4062:L
4056:s
4033:}
4024:)
4020:L
4017:(
4005:u
4002:,
3999:t
3989:u
3986:t
3983:=
3980:s
3974:|
3968:t
3965:{
3962:=
3959:)
3956:s
3953:(
3945:L
3901:)
3898:a
3892:s
3889:(
3876:=
3873:a
3867:)
3864:s
3861:(
3818:=
3815:a
3776:b
3770:a
3758:a
3755:)
3752:b
3746:s
3743:(
3736:b
3733:=
3730:a
3718:s
3712:{
3707:=
3704:b
3698:)
3695:a
3692:s
3689:(
3666:a
3660:s
3650:s
3646:a
3642:s
3638:a
3610:S
3606:M
3589:}
3586:M
3580:m
3574:|
3568:m
3564:/
3560:S
3557:{
3531:}
3528:t
3524:/
3520:S
3517:=
3514:s
3510:/
3506:S
3500:|
3494:M
3488:M
3482:)
3479:t
3476:,
3473:s
3470:(
3467:{
3463:=
3456:S
3438:S
3413:M
3393:M
3387:S
3365:2
3362:L
3354:2
3351:L
3347:1
3344:L
3337:b
3333:a
3329:s
3325:}
3323:1
3320:L
3318:∈
3312:2
3309:L
3307:∈
3305:t
3301:s
3297:2
3294:L
3292:/
3290:1
3287:L
3282:2
3279:L
3275:1
3272:L
3268:2
3265:L
3263:/
3261:1
3258:L
3235:}
3232:S
3226:a
3223:s
3217:|
3211:M
3205:s
3202:{
3199:=
3196:a
3192:/
3188:S
3165:M
3145:M
3139:S
3113:=
3110:a
3106:/
3069:b
3063:a
3044:b
3041:=
3038:a
3026:s
3020:{
3015:=
3012:b
3008:/
3004:)
3001:a
2998:s
2995:(
2982:a
2968:a
2964:/
2960:s
2950:s
2946:a
2942:s
2938:a
2912:}
2909:L
2903:s
2897:|
2891:)
2888:s
2885:(
2872:{
2869:=
2866:)
2863:L
2860:(
2837:L
2769:a
2759:a
2756:t
2753:=
2750:s
2738:a
2735:)
2732:t
2729:(
2706:a
2696:a
2693:t
2690:=
2687:s
2675:)
2672:t
2669:(
2642:=
2639:s
2621:{
2616:=
2613:)
2610:s
2607:(
2573:)
2570:s
2567:(
2527:s
2499:s
2473:g
2466:g
2459:g
2457:(
2452:g
2446:.
2441:g
2434:g
2427:g
2418:g
2411:g
2404:g
2397:g
2387:g
2380:g
2373:g
2362:g
2331:a
2311:)
2308:a
2305:(
2302:f
2276:L
2254:)
2251:)
2248:L
2245:(
2242:f
2239:(
2234:1
2227:f
2220:L
2196:L
2190:)
2187:)
2184:L
2181:(
2176:1
2169:f
2165:(
2162:f
2140:L
2134:)
2131:)
2128:L
2125:(
2120:1
2113:f
2109:(
2106:f
2084:}
2081:L
2075:)
2072:s
2069:(
2066:f
2060:s
2057:{
2054:=
2051:)
2048:L
2045:(
2040:1
2033:f
2010:L
1988:}
1985:s
1982:=
1979:)
1976:w
1973:(
1970:f
1964:w
1961:{
1958:=
1955:)
1952:s
1949:(
1944:1
1937:f
1914:s
1890:L
1866:)
1863:L
1860:(
1857:f
1837:L
1798:a
1778:s
1758:s
1755:=
1752:)
1749:a
1746:(
1743:f
1709:f
1699:f
1688:f
1679:f
1670:f
1660:f
1610:›
1608:ß
1606:‹
1596:A
1591:›
1589:A
1587:‹
1577:A
1572:›
1570:a
1568:‹
1561:)
1559:x
1557:(
1552:f
1547:x
1524:f
1497:)
1494:s
1491:(
1488:f
1483:L
1477:s
1469:=
1466:)
1463:L
1460:(
1457:f
1444:a
1440:L
1436:s
1430:)
1428:a
1426:(
1424:f
1422:)
1420:s
1418:(
1416:f
1410:(
1408:f
1393:f
1382:a
1378:L
1373:a
1369:L
1365:a
1363:(
1361:f
1357:a
1353:f
1337:L
1315:D
1309:D
1303:D
1279:D
1253:o
1250:a
1247:c
1244:a
1241:c
1218:}
1212:o
1206:,
1200:c
1194:,
1188:a
1182:{
1159:)
1156:s
1153:(
1142:S
1136:s
1128:=
1125:)
1122:S
1119:(
1093:S
1073:S
1047:)
1044:s
1041:(
1018:s
992:D
986:D
980:D
960:}
954:9
948:,
942:8
936:,
930:7
924:,
918:6
912:,
906:5
900:,
894:4
888:,
882:3
876:,
870:2
864:,
858:1
852:,
846:0
840:{
837:=
834:D
811:U
805:)
802:T
796:S
793:(
790:=
787:)
784:U
778:T
775:(
769:S
749:S
743:}
740:{
737:=
734:}
731:{
728:=
725:}
722:{
716:S
696:S
690:}
684:{
681:=
678:S
675:=
672:}
666:{
660:S
640:}
637:{
617:}
611:{
568:}
565:T
559:t
553:S
547:s
541:t
535:s
532:{
529:=
526:T
520:S
500:T
480:S
460:T
454:S
434:T
414:S
384:h
381:a
378:l
375:b
369:=
363:h
360:a
348:l
345:b
339:=
336:)
330:h
327:a
315:(
309:)
303:l
291:b
285:(
262:u
256:)
253:t
247:s
244:(
241:=
238:)
235:u
229:t
226:(
220:s
196:s
187:=
184:s
181:=
172:s
152:t
149:s
129:t
123:s
103:t
83:s
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.