45:
1104:
1054:
1126:
783:
742:
of a string is not equal to the string itself; some sources in addition restrict a proper prefix to be non-empty. A prefix can be seen as a special case of a substring.
938:
of a string is not equal to the string itself. A more restricted interpretation is that it is also not empty. A suffix can be seen as a special case of a substring.
974:
is a simplified version of this data structure that lists the start positions of the suffixes in alphabetically sorted order; it has many of the same applications.
391:
932:
736:
527:
501:
475:
443:
417:
1166:
1146:
1032:
1012:
903:
883:
863:
823:
803:
707:
687:
667:
613:
593:
550:
359:
339:
319:
299:
204:
184:
164:
144:
124:
1300:
1059:
1278:
1253:
1228:
624:
31:
982:
A border is suffix and prefix of the same string, e.g. "bab" is a border of "babab" (and also of "baboon eating a kebab").
620:
30:
This article is about the definition of a substring. For the computer function which performs this operation, see
1305:
967:
77:
619:, which is a more general concept. The occurrences of a given pattern in a given string can be found with a
1037:
73:
1109:
762:
623:. Finding the longest string which is equal to a substring of two or more strings is known as the
1274:
1249:
1224:
644:
1194:
1172:
1168:. Finding superstrings whose length is as small as possible is a more interesting problem.
65:
1171:
A string that contains every possible permutation of a specified character set is called a
364:
1189:
908:
830:
826:
712:
61:
17:
966:
that represents all of its suffixes. Suffix trees have large numbers of applications in
509:
483:
457:
425:
399:
1184:
1151:
1131:
1017:
997:
963:
888:
868:
848:
808:
788:
692:
672:
652:
598:
578:
535:
344:
324:
304:
284:
189:
169:
149:
129:
109:
1271:
Algorithms on
Strings, Trees and Sequences: Computer Science and Computational Biology
1294:
971:
834:
270:
956:
616:
38:
759:
The square subset symbol is sometimes used to indicate a prefix, so that
44:
945:
is equal to a suffix (and substring and subsequence) of the string
749:
is equal to a prefix (and substring and subsequence) of the string
563:
of the string, and equivalently a suffix of a prefix; for example,
393:. In particular, the empty string is a substring of every string.
43:
1099:{\displaystyle P=\{{\text{abcc}},{\text{efab}},{\text{bccla}}\}}
960:
1148:, in arbitrary order, always obtains a trivial superstring of
627:. In the mathematical literature, substrings are also called
1014:
of strings is a single string that contains every string in
106:
are special cases of substrings. A prefix of a string
1154:
1134:
1112:
1062:
1040:
1020:
1000:
911:
891:
871:
851:
811:
791:
765:
715:
695:
675:
655:
601:
581:
538:
512:
486:
460:
428:
402:
367:
347:
327:
307:
287:
192:
172:
152:
132:
112:
1160:
1140:
1120:
1098:
1048:
1026:
1006:
926:
897:
877:
857:
817:
797:
777:
730:
701:
681:
661:
607:
587:
544:
521:
495:
469:
437:
411:
385:
353:
333:
313:
293:
198:
178:
158:
138:
118:
506:, while the second occurrence is obtained with
1128:is a shorter one. Concatenating all members of
1246:Automata and Formal Languages: An Introduction
422:is equal to substrings (and subsequences) of
8:
1093:
1069:
1223:. Cambridge: Cambridge University Press.
1153:
1133:
1113:
1111:
1088:
1080:
1072:
1061:
1041:
1039:
1019:
999:
910:
890:
870:
850:
810:
790:
764:
714:
694:
674:
654:
600:
580:
537:
511:
485:
459:
427:
401:
366:
346:
326:
306:
286:
191:
186:is a substring that occurs at the end of
171:
151:
131:
111:
27:Contiguous part of a sequence of symbols
1248:. London: Prentice-Hall International.
1214:
1212:
1210:
1206:
301:is a substring (or factor) of a string
454:The first occurrence is obtained with
1049:{\displaystyle {\text{bcclabccefab}}}
7:
451:banana ||||| ana|| ||| ana
1273:. US: Cambridge University Press.
25:
1121:{\displaystyle {\text{efabccla}}}
645:String operations § Prefixes
166:; likewise, a suffix of a string
833:, which is a particular kind of
625:longest common substring problem
146:that occurs at the beginning of
41:, a generalization of substring.
571:, which is in turn a suffix of
778:{\displaystyle p\sqsubseteq t}
209:The substrings of the string "
32:String functions (programming)
1:
1034:as a substring. For example,
555:A substring of a string is a
321:if there exists two strings
72:is a contiguous sequence of
560:
556:
1322:
642:
621:string searching algorithm
448:at two different offsets:
36:
29:
1301:String (computer science)
885:if there exists a string
689:if there exists a string
18:Suffix (computer science)
865:is a suffix of a string
669:is a prefix of a string
552:being the empty string.
96:", but not a substring.
94:It was the best of times
86:It was the best of times
37:Not to be confused with
1269:Gusfield, Dan (1999) .
829:on strings, called the
92:" is a subsequence of "
1221:Combinatorics on words
1162:
1142:
1122:
1100:
1050:
1028:
1008:
928:
899:
879:
859:
819:
799:
779:
732:
703:
683:
663:
609:
589:
546:
523:
497:
471:
439:
413:
387:
355:
335:
315:
295:
200:
180:
160:
140:
120:
62:formal language theory
57:
1244:Kelley, Dean (1995).
1219:Lothaire, M. (1997).
1163:
1143:
1123:
1101:
1051:
1029:
1009:
952:banana |||| nana
929:
900:
880:
860:
820:
800:
780:
733:
704:
684:
664:
610:
590:
547:
524:
498:
472:
440:
414:
388:
386:{\displaystyle t=pus}
356:
336:
316:
296:
201:
181:
161:
141:
121:
84:" is a substring of "
52:" is a substring of "
47:
1152:
1132:
1110:
1060:
1056:is a superstring of
1038:
1018:
998:
941:Example: The string
927:{\displaystyle t=ps}
909:
889:
869:
849:
809:
789:
763:
745:Example: The string
731:{\displaystyle t=ps}
713:
693:
673:
653:
599:
579:
536:
510:
484:
458:
426:
400:
396:Example: The string
365:
345:
325:
305:
285:
190:
170:
150:
130:
110:
1158:
1138:
1118:
1096:
1046:
1024:
1004:
959:for a string is a
924:
895:
875:
855:
815:
795:
775:
728:
699:
679:
659:
605:
595:is a substring of
585:
542:
522:{\displaystyle p=}
519:
496:{\displaystyle s=}
493:
470:{\displaystyle p=}
467:
438:{\displaystyle t=}
435:
412:{\displaystyle u=}
409:
383:
351:
331:
311:
291:
196:
176:
156:
136:
126:is a substring of
116:
58:
1161:{\displaystyle P}
1141:{\displaystyle P}
1116:
1091:
1083:
1075:
1044:
1027:{\displaystyle P}
1007:{\displaystyle P}
968:string algorithms
898:{\displaystyle p}
878:{\displaystyle t}
858:{\displaystyle s}
825:. This defines a
818:{\displaystyle t}
798:{\displaystyle p}
702:{\displaystyle s}
682:{\displaystyle t}
662:{\displaystyle p}
608:{\displaystyle t}
588:{\displaystyle u}
545:{\displaystyle s}
354:{\displaystyle s}
334:{\displaystyle p}
314:{\displaystyle t}
294:{\displaystyle u}
269:", "" (note the
199:{\displaystyle S}
179:{\displaystyle S}
159:{\displaystyle S}
139:{\displaystyle S}
119:{\displaystyle S}
88:". In contrast, "
80:. For instance, "
16:(Redirected from
1313:
1306:Formal languages
1285:
1284:
1266:
1260:
1259:
1241:
1235:
1234:
1216:
1195:Suffix automaton
1173:superpermutation
1167:
1165:
1164:
1159:
1147:
1145:
1144:
1139:
1127:
1125:
1124:
1119:
1117:
1114:
1105:
1103:
1102:
1097:
1092:
1089:
1084:
1081:
1076:
1073:
1055:
1053:
1052:
1047:
1045:
1042:
1033:
1031:
1030:
1025:
1013:
1011:
1010:
1005:
994:of a finite set
948:
944:
933:
931:
930:
925:
904:
902:
901:
896:
884:
882:
881:
876:
864:
862:
861:
856:
824:
822:
821:
816:
804:
802:
801:
796:
784:
782:
781:
776:
752:
748:
737:
735:
734:
729:
708:
706:
705:
700:
688:
686:
685:
680:
668:
666:
665:
660:
631:(in America) or
614:
612:
611:
606:
594:
592:
591:
586:
574:
570:
566:
551:
549:
548:
543:
531:
528:
526:
525:
520:
505:
502:
500:
499:
494:
479:
476:
474:
473:
468:
447:
444:
442:
441:
436:
421:
418:
416:
415:
410:
392:
390:
389:
384:
360:
358:
357:
352:
340:
338:
337:
332:
320:
318:
317:
312:
300:
298:
297:
292:
205:
203:
202:
197:
185:
183:
182:
177:
165:
163:
162:
157:
145:
143:
142:
137:
125:
123:
122:
117:
66:computer science
21:
1321:
1320:
1316:
1315:
1314:
1312:
1311:
1310:
1291:
1290:
1289:
1288:
1281:
1268:
1267:
1263:
1256:
1243:
1242:
1238:
1231:
1218:
1217:
1208:
1203:
1190:Substring index
1181:
1150:
1149:
1130:
1129:
1108:
1107:
1058:
1057:
1036:
1035:
1016:
1015:
996:
995:
988:
980:
953:
946:
942:
907:
906:
887:
886:
867:
866:
847:
846:
843:
831:prefix relation
827:binary relation
807:
806:
805:is a prefix of
787:
786:
761:
760:
757:
756:banana ||| ban
750:
746:
711:
710:
691:
690:
671:
670:
651:
650:
647:
641:
615:, it is also a
597:
596:
577:
576:
572:
568:
567:is a prefix of
564:
534:
533:
529:
508:
507:
503:
482:
481:
477:
456:
455:
452:
445:
424:
423:
419:
398:
397:
363:
362:
343:
342:
323:
322:
303:
302:
283:
282:
279:
188:
187:
168:
167:
148:
147:
128:
127:
108:
107:
42:
35:
28:
23:
22:
15:
12:
11:
5:
1319:
1317:
1309:
1308:
1303:
1293:
1292:
1287:
1286:
1279:
1261:
1254:
1236:
1229:
1205:
1204:
1202:
1199:
1198:
1197:
1192:
1187:
1185:Brace notation
1180:
1177:
1157:
1137:
1095:
1087:
1079:
1071:
1068:
1065:
1023:
1003:
987:
984:
979:
976:
964:data structure
951:
923:
920:
917:
914:
894:
874:
854:
842:
839:
814:
794:
774:
771:
768:
755:
727:
724:
721:
718:
698:
678:
658:
640:
637:
635:(in Europe).
604:
584:
541:
518:
515:
492:
489:
466:
463:
450:
434:
431:
408:
405:
382:
379:
376:
373:
370:
350:
330:
310:
290:
278:
275:
195:
175:
155:
135:
115:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
1318:
1307:
1304:
1302:
1299:
1298:
1296:
1282:
1280:0-521-58519-8
1276:
1272:
1265:
1262:
1257:
1255:0-13-497777-7
1251:
1247:
1240:
1237:
1232:
1230:0-521-59924-5
1226:
1222:
1215:
1213:
1211:
1207:
1200:
1196:
1193:
1191:
1188:
1186:
1183:
1182:
1178:
1176:
1174:
1169:
1155:
1135:
1085:
1077:
1066:
1063:
1021:
1001:
993:
985:
983:
977:
975:
973:
969:
965:
962:
958:
950:
939:
937:
936:proper suffix
921:
918:
915:
912:
892:
872:
852:
840:
838:
836:
832:
828:
812:
792:
785:denotes that
772:
769:
766:
754:
743:
741:
740:proper prefix
725:
722:
719:
716:
696:
676:
656:
646:
638:
636:
634:
630:
626:
622:
618:
602:
582:
562:
558:
553:
539:
516:
513:
490:
487:
464:
461:
449:
432:
429:
406:
403:
394:
380:
377:
374:
371:
368:
348:
328:
308:
288:
276:
274:
273:at the end).
272:
268:
264:
260:
256:
252:
248:
244:
240:
236:
232:
228:
224:
220:
216:
213:" would be: "
212:
207:
193:
173:
153:
133:
113:
105:
101:
97:
95:
91:
87:
83:
79:
75:
71:
67:
63:
55:
51:
46:
40:
33:
19:
1270:
1264:
1245:
1239:
1220:
1170:
1043:bcclabccefab
991:
989:
981:
972:suffix array
954:
940:
935:
844:
835:prefix order
758:
744:
739:
648:
632:
628:
554:
453:
395:
280:
271:empty string
266:
262:
258:
254:
250:
246:
242:
238:
234:
230:
226:
222:
218:
214:
210:
208:
103:
99:
98:
93:
89:
85:
81:
69:
59:
53:
49:
992:superstring
986:Superstring
957:suffix tree
617:subsequence
82:the best of
39:subsequence
1295:Categories
1201:References
905:such that
709:such that
643:See also:
361:such that
90:Itwastimes
74:characters
845:A string
770:⊑
649:A string
281:A string
277:Substring
76:within a
70:substring
54:substring
1179:See also
1115:efabccla
629:subwords
104:suffixes
100:Prefixes
633:factors
1277:
1252:
1227:
1106:, and
978:Border
970:. The
947:banana
841:Suffix
751:banana
639:Prefix
573:banana
561:suffix
557:prefix
446:banana
78:string
50:string
1090:bccla
575:. If
559:of a
231:apple
211:apple
1275:ISBN
1250:ISBN
1225:ISBN
1082:efab
1074:abcc
961:trie
943:nana
934:. A
738:. A
569:nana
532:and
480:and
341:and
261:", "
257:", "
253:", "
249:", "
247:pple
245:", "
241:", "
237:", "
233:", "
229:", "
227:appl
225:", "
221:", "
217:", "
102:and
68:, a
64:and
747:ban
565:nan
530:ban
420:ana
265:" "
255:ple
243:ppl
223:app
60:In
1297::
1209:^
1175:.
990:A
955:A
949::
837:.
753::
504:na
263:le
251:pl
239:pp
219:ap
206:.
1283:.
1258:.
1233:.
1156:P
1136:P
1094:}
1086:,
1078:,
1070:{
1067:=
1064:P
1022:P
1002:P
922:s
919:p
916:=
913:t
893:p
873:t
853:s
813:t
793:p
773:t
767:p
726:s
723:p
720:=
717:t
697:s
677:t
657:p
603:t
583:u
540:s
517:=
514:p
491:=
488:s
478:b
465:=
462:p
433:=
430:t
407:=
404:u
381:s
378:u
375:p
372:=
369:t
349:s
329:p
309:t
289:u
267:e
259:l
235:p
215:a
194:S
174:S
154:S
134:S
114:S
56:"
48:"
34:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
