279:
Usually, the trial check will quickly reject the trial match. If the strings are uniformly distributed random letters, then the chance that characters match is 1 in 26. In most cases, the trial check will reject the match at the initial letter. The chance that the first two letters will match is 1 in
2187:
The example above illustrates the general technique for assembling the table with a minimum of fuss. The principle is that of the overall search: most of the work was already done in getting to the current position, so very little needs to be done in leaving it. The only minor complication is that
1305:
of the pattern, we know exactly at which places a new potential match which could continue to the current position could begin prior to the current position. In other words, we "pre-search" the pattern itself and compile a list of all possible fallback positions that bypass a maximum of hopeless
335:
character. The simple string-matching algorithm will now examine 1000 characters at each trial position before rejecting the match and advancing the trial position. The simple string search example would now take about 1000 character comparisons times 1 million positions for 1 billion character
2931:
I learned in 2012 that Yuri
Matiyasevich had anticipated the linear-time pattern matching and pattern preprocessing algorithms of this paper, in the special case of a binary alphabet, already in 1969. He presented them as constructions for a Turing machine with a two-dimensional working
650:
that could be the beginning of a new match, so the algorithm must take this into consideration. As these characters match the two characters prior to the current position, those characters need not be checked again; the algorithm sets
208:
discovered a similar algorithm, coded by a two-dimensional Turing machine, while studying a string-pattern-matching recognition problem over a binary alphabet. This was the first linear-time algorithm for string matching.
180:
by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin, thus bypassing re-examination of previously matched characters.
2678:
in the text need not be checked again in the next phase, and so only a constant number of operations are executed between the processing of each index of the text. This satisfies the real-time computing restriction.
956:: an integer, j ← 0 (the position of the current character in S) an integer, k ← 0 (the position of the current character in W) an array of integers, T (the table, computed elsewhere)
2209:: an integer, pos ← 1 (the current position we are computing in T) an integer, cnd ← 0 (the zero-based index in W of the next character of the current candidate substring)
382:
The difference is that KMP makes use of previous match information that the straightforward algorithm does not. In the example above, when KMP sees a trial match fail on the 1000th character (
1452:. Hence at each stage, the shortcut rule is that one needs to consider checking suffixes of a given size m+1 only if a valid suffix of size m was found at the previous stage (i.e.
1337:. We use the convention that the empty string has length 0. Since a mismatch at the very start of the pattern is a special case (there is no possibility of backtracking), we set
1420:, we first check the proper suffix of length 1, and as in the previous case it fails. Should we also check longer suffixes? No, we now note that there is a shortcut to checking
418:
to 998. KMP maintains its knowledge in the precomputed table and two state variables. When KMP discovers a mismatch, the table determines how much KMP will increase (variable
1301:
more than once. The key observation about the nature of a linear search that allows this to happen is that in having checked some segment of the main string against an
149:
108:
79:
359:
The KMP algorithm has a better worst-case performance than the straightforward algorithm. KMP spends a little time precomputing a table (on the order of the size of
2509:
2480:
2296:
2447:
2421:
2362:
2742:
2722:
2676:
2656:
2636:
2616:
2596:
2576:
2316:
2682:
3068:. Wiley-Interscience Series in Discrete Mathematics and Optimization. With a foreword by Philippe Flajolet. Chichester: Wiley. pp. 15–17, 136–141.
1474:. The same logic shows that the longest substring we need to consider has length 1, and as in the previous case it fails since "D" is not a prefix of
2188:
the logic which is correct late in the string erroneously gives non-proper substrings at the beginning. This necessitates some initialization code.
252:. If a match is found, the algorithm tests the other characters in the word being searched by checking successive values of the word position index,
3745:
2904:
2558:
version of KMP can be implemented using a separate failure function table for each character in the alphabet. If a mismatch occurs on character
1459:
Therefore, we need not even concern ourselves with substrings having length 2, and as in the previous case the sole one with length 1 fails, so
3613:
280:
26 (1 in 26^2 chances of a match over 26 possible letters). So if the characters are random, then the expected complexity of searching string
3430:
1285:, that is to say, for any failure, we can only roll back as much as we have progressed up to the failure. Then it is clear the runtime is 2
659:(signaling the first two characters match) and continues matching. Thus the algorithm not only omits previously matched characters of
3325:
2686:
315:
may take many character comparisons. The worst case is if the two strings match in all but the last letter. Imagine that the string
3364:
3127:
871:
The above example contains all the elements of the algorithm. For the moment, we assume the existence of a "partial match" table
3290:
3554:
3295:
2393:. This means that the inner loop can execute at most as many times in total, as the outer loop has executed – each decrease of
915:
is a mismatch, we cannot backtrack and must simply check the next character; and second, although the next possible match will
3730:
2825:
1357:
first. We will see that it follows much the same pattern as the main search, and is efficient for similar reasons. We set
1062:. Except for the fixed overhead incurred in entering and exiting the function, all the computations are performed in the
3833:
952:: an array of integers, P (positions in S at which W is found) an integer, nP (number of positions)
3511:
3285:
1103:
times, since at each iteration it executes one of the two branches in the loop. The first branch invariably increases
3151:
948:: an array of characters, S (the text to be searched) an array of characters, W (the word sought)
204:
published a technical report in 1970. The three also published the algorithm jointly in 1977. Independently, in 1969,
3379:
3320:
3192:
3073:
3043:
3010:
2857:
398:
characters before discovering a mismatch at the 1000th character (position 999). Advancing the trial match position
3227:
2944:
Amir, Amihood; Landau, Gad M.; Lewenstein, Moshe; Sokol, Dina (2007). "Dynamic text and static pattern matching".
554:; hence, having checked all those characters previously (and knowing they matched the corresponding characters in
3750:
3620:
3578:
2397:
by 1 in the inner loop needs to have a corresponding increase by 1 in the outer loop. Since the outer loop takes
1033:
2618:
in the pattern at which the mismatch took place. This will return the length of the longest substring ending at
3407:
3165:
879:, which indicates where we need to look for the start of a new match when a mismatch is found. The entries of
3792:
3761:
3412:
3267:
308:
is 1000 characters, then the string search should complete after about 1.04 million character comparisons.
115:
45:
3491:
3217:
1131:
of the beginning of the current potential match is increased. At the same time, the second branch leaves
394:
by 1, but it will know that the first 998 characters at the new position already match. KMP matched 999
990:(occurrence found, if only first occurrence is needed, m ← j - k may be returned here)
447:= "ABC ABCDAB ABCDABCDABDE". At any given time, the algorithm is in a state determined by two integers:
3843:
3547:
3496:
3374:
3341:
3277:
169:
28:
2724:
is the length of the pattern, which is the string we are searching for in the text which is of length
439:
To illustrate the algorithm's details, consider a (relatively artificial) run of the algorithm, where
3592:
3506:
3402:
3346:
3247:
3201:
2876:
38:
907:
is the amount of "backtracking" we need to do after a mismatch). This has two implications: first,
3740:
3501:
3305:
3237:
3002:
2781:
2638:
matching a prefix of the pattern, with the added condition that the character after the prefix is
1321:
that just failed to match; this is how far we have to backtrack in finding the next match. Hence
311:
That expected performance is not guaranteed. If the strings are not random, then checking a trial
276:
reaches the end of the string then there is no match, in which case the search is said to "fail".
3756:
3585:
3450:
3097:
876:
248:
the algorithm first checks for equality of the first character in the word being searched, i.e.
125:
84:
55:
3725:
3650:
3606:
2776:
1292:
3838:
3802:
3540:
3455:
3397:
3257:
3185:
3033:
2865:Записки научных семинаров Ленинградского отделения Математического института им. В.А.Стеклова
2994:
2767:
Knuth, Donald; Morris, James H.; Pratt, Vaughan (1977). "Fast pattern matching in strings".
3812:
3694:
3599:
3262:
3061:
2982:
1261:), the text pointer is kept still, while the word pointer is rolled back a certain amount (
3083:
3053:
3020:
2485:
2456:
2272:
1436:
with length 2 (the maximum possible); then its first character is also a proper prefix of
725:). As in the first trial, the mismatch causes the algorithm to return to the beginning of
558:), there is no chance of finding the beginning of a match. Therefore, the algorithm sets
8:
3460:
2995:
2555:
2426:
2400:
2341:
1317:
leading up to (but not including) that position, other than the full segment starting at
646:. However, just prior to the end of the current partial match, there was that substring
3782:
3389:
3356:
3115:
2961:
2896:
2727:
2707:
2661:
2641:
2621:
2601:
2581:
2561:
2389:
gets decreased by at least 1 in each inner loop iteration; the inner loop condition is
2301:
233:
2817:
3521:
3069:
3039:
3006:
2900:
2821:
1036:
205:
3516:
3486:
3440:
3242:
3178:
3079:
3049:
3016:
2986:
2978:
2965:
2953:
2888:
2813:
2786:
240:, i.e. the position in the string being searched that corresponds to the character
157:
118:
16:
Algorithm for finding sub-text location(s) inside a given sentence in Big O(n) time
3121:
2845:(Technical report). University of California, Berkeley, Computation Center. TR-40.
1257:
by 1. Upon failure, that is, the word and the text do not match at the positions (
3797:
3679:
3369:
3310:
3222:
3155:
3029:
197:
189:
48:
3102:
3684:
3422:
3315:
3110:
2990:
2538:
These complexities are the same, no matter how many repetitive patterns are in
2512:
1342:
1059:
3138:
3133:
1584:. Furthermore, the same argument as above shows that we need not look before
1432:(a proper prefix of a string is not equal to the string itself) and ending at
1297:
The goal of the table is to allow the algorithm not to match any character of
3827:
3777:
3232:
3209:
2689:. The failure function is progressively calculated as the string is rotated.
2182:
1221:
Here is another way to think about the runtime: Let us say we begin to match
201:
3143:
2957:
2523:
Since the two portions of the algorithm have, respectively, complexities of
1506:; we should begin at 1 position ahead. This means that we may shift pattern
1429:
1425:
1366:
1127:, and as we have seen, this is always a positive number. Thus the location
1088:. In particular, the next possible match must occur at a higher index than
272:, then a match is found at that position in the search string. If the index
3563:
3435:
3252:
3160:
3148:
1572:
Finally, we see that the next character in the ongoing segment starting at
371:)), and then it uses that table to do an efficient search of the string in
193:
2338:
is increased by 1 in every iteration of the loop. Thus the loop will take
1195:, so that since it increases by unit increments at most, we must have had
3787:
3445:
3106:
1249:. Upon success, that is, the word and the text matched at the positions (
859:
This time the match is complete, and the first character of the match is
2892:
932:
2685:
uses a modified version of the KMP preprocessing function to find the
1203:
at some point in the past, and therefore either way we would be done.
3717:
3674:
866:
260:
in the word being searched and checks for equality of the expression
185:
2790:
1306:
characters while not sacrificing any potential matches in doing so.
3644:
3631:
2804:
Knuth, Donald E. (1973). "The
Dangers of Computer-Science Theory".
1210:
times, showing that the time complexity of the search algorithm is
1068:
loop. To bound the number of iterations of this loop; observe that
488:
if they are equal. This is depicted, at the start of the run, like
2201:: an array of characters, W (the word to be analyzed)
1348:
236:" or "naive" algorithm, is to look for a word match at each index
3807:
3481:
923:, as in the example above, we need not actually check any of the
591:
This match fails at the initial character, so the algorithm sets
1525:: though by inspection the longest substring would appear to be
3532:
3166:
KMP algorithm search time complexity explained in plain
English
2205:: an array of integers, T (the table to be filled)
3118:
description and C code by
Christian Charras and Thierry Lecroq
2377:
and gets increased by at most 1 in each outer loop iteration.
1815:
Another example (slightly changed from the previous example):
468:, denoting the index of the currently considered character in
2264:
2261:
T ← cnd (only needed when all word occurrences are searched)
1032:, the search portion of the Knuth–Morris–Pratt algorithm has
729:
and begins searching at the mismatched character position of
217:
A string-matching algorithm wants to find the starting index
1163:; therefore, each branch of the loop can be reached at most
3707:
3666:
3655:
3465:
841:
1 2 m: 01234567890123456789012 S: ABC ABCDAB ABCD
3170:
2993:(2001). "Section 32.4: The Knuth-Morris-Pratt algorithm".
2977:
2269:
The time (and space) complexity of the table algorithm is
2183:
Description of pseudocode for the table-building algorithm
927:
characters after that, so that we continue searching from
709:
This search at the new position fails immediately because
3702:
3639:
2943:
1545:, and we can assume that the corresponding character in
1313:, the length of the longest possible initial segment of
1293:"Partial match" table (also known as "failure function")
3001:(Second ed.). MIT Press and McGraw-Hill. pp.
883:
are constructed so that if we have a match starting at
782:
1 2 m: 01234567890123456789012 S: ABC ABCDAB
2858:"О распознавании в реальное время отношения вхождения"
2578:
in the text, the failure function table for character
1153:
new_m + new_i = old_m + old_i - T + T = old_m + old_i
745:
1 2 m: 01234567890123456789012 S: ABC ABCDAB
2730:
2710:
2664:
2644:
2624:
2604:
2584:
2564:
2488:
2459:
2429:
2403:
2344:
2304:
2275:
1502:. Thus there is no point in restarting the search at
1099:
This fact implies that the loop can execute at most 2
1072:
is constructed so that if a match which had begun at
1023:
128:
87:
58:
3038:. River Edge, NJ: World Scientific. pp. 20–25.
1309:
We want to be able to look up, for each position in
679:
1 2 m: 01234567890123456789012 S: ABC ABCD
3149:
Transformation between different forms of algorithm
2924:Knuth mentions this fact in the errata of his book
2806:
1333:which is also a segment of the substring ending at
895:, then the next possible match will start at index
837:, and continue matching from the current position.
2736:
2716:
2670:
2650:
2630:
2610:
2590:
2570:
2518:
2503:
2474:
2441:
2415:
2356:
2310:
2290:
867:Description of pseudocode for the search algorithm
434:
232:The most straightforward algorithm, known as the "
143:
102:
73:
2877:"Real-time recognition of the inclusion relation"
2453:Combined, the outer and inner loops take at most
2423:iterations, the inner loop can take no more than
3825:
3066:Average case analysis of algorithms on sequences
3027:
2766:
1456:) and should not bother to check m+2, m+3, etc.
602:1 2 m: 01234567890123456789012 S: ABC
522:The algorithm compares successive characters of
1444:, which we already determined did not occur as
1440:, hence a proper prefix itself, and it ends at
1349:Working example of the table-building algorithm
1167:times, since they respectively increase either
770:fails immediately, so the algorithm next tries
570:1 2 m: 01234567890123456789012 S: ABC
3614:Things a Computer Scientist Rarely Talks About
1325:is exactly the length of the longest possible
530:, moving from one to the next by incrementing
319:consists of 1 million characters that are all
300:). The expected performance is very good. If
3548:
3186:
2531:, the complexity of the overall algorithm is
1405:. However "B" is not a prefix of the pattern
1084:, then the next possible match must begin at
667:), but also previously matched characters of
422:) and where it will resume testing (variable
2874:
1269:is the jump table), and we attempt to match
935:implementation of the KMP search algorithm.
542:. Rather than beginning to search again at
534:if they match. However, in the fourth step
492:1 2 m: 01234567890123456789012 S:
414:and does not retest them; that is, KMP sets
3060:
2840:
2762:
2760:
2330:is initialized to 1, the loop condition is
1599:Therefore, we compile the following table:
1541:itself extends the prefix match begun with
825:. Reasoning as before, the algorithm sets
630:increments through a nearly complete match
3555:
3541:
3193:
3179:
3161:Knuth-Morris-Pratt algorithm written in C#
2855:
2265:Efficiency of the table-building algorithm
1424:suffixes: let us say that we discovered a
1115:of the currently scrutinized character of
1028:Assuming the prior existence of the table
172:that searches for occurrences of a "word"
3122:Explanation of the algorithm from scratch
2780:
2687:lexicographically minimal string rotation
264:. If all successive characters match in
3813:Potrzebie system of weights and measures
3365:Comparison of regular-expression engines
2926:Selected Papers on Design of Algorithms
2757:
833:leading up to the current position, set
256:. The algorithm retrieves the character
3746:Robinson–Schensted–Knuth correspondence
1510:by match length plus one character, so
994:P ← j - k, nP ← nP + 1
829:, to start at the two-character string
3826:
3035:Jewels of stringology. Text algorithms
1377:. But there are no proper suffixes of
1119:is increased. The second branch adds
655:(the start of the initial prefix) and
3536:
3326:Zhu–Takaoka string matching algorithm
3174:
2803:
1277:. The maximum number of roll-back of
817:, does not match the final character
344:, then the worst-case performance is
1517:Considering now the next character,
550:occurs between positions 1 and 2 in
476:In each step the algorithm compares
3291:Boyer–Moore string-search algorithm
2843:A linear pattern-matching algorithm
2841:Morris, J.H. Jr; Pratt, V. (1970).
2658:. With this restriction, character
1143:added to it, and immediately after
13:
3128:Breaking down steps of running KMP
1932:Another more complicated example:
1592:, so that this is it, and we take
1533:. The reasoning is similar to why
1482:, we can do better by noting that
1373:which is also a prefix of pattern
1147:gets assigned as the new value of
1024:Efficiency of the search algorithm
809:Once again, the algorithm matches
331:characters terminating in a final
129:
88:
59:
14:
3855:
3731:Knuth–Bendix completion algorithm
3380:Nondeterministic finite automaton
3321:Two-way string-matching algorithm
3098:String Searching Applet animation
3091:
2257:pos ← pos + 1, cnd ← cnd + 1
3562:
3139:LogicFirst YouTube lecture video
2482:iterations. This corresponds to
1206:Thus the loop executes at most 2
458:where the prospective match for
429:
192:and independently discovered by
3579:The Art of Computer Programming
3103:An explanation of the algorithm
2907:from the original on 2021-04-30
2519:Efficiency of the KMP algorithm
1498:, was a mismatch and therefore
454:, denoting the position within
435:Example of the search algorithm
336:comparisons. If the length of
3296:Boyer–Moore–Horspool algorithm
3286:Apostolico–Giancarlo algorithm
3134:NPTELHRD YouTube lecture video
2937:
2918:
2849:
2834:
2797:
2699:
2498:
2492:
2285:
2279:
998:k ← T (T can't be -1)
138:
132:
97:
91:
68:
62:
1:
2881:Journal of Soviet Mathematics
2873:, translated into English as
2818:10.1016/S0049-237X(09)70357-X
2750:
1486:, and also that a look-up of
931:. The following is a sample
406:, so KMP knows there are 998
402:by one throws away the first
225:that matches the search word
212:
3736:Knuth–Morris–Pratt algorithm
3301:Knuth–Morris–Pratt algorithm
3228:Damerau–Levenshtein distance
3116:Knuth-Morris-Pratt algorithm
1389:, we see that the substring
526:to "parallel" characters of
304:is 1 million characters and
176:within a main "text string"
162:Knuth–Morris–Pratt algorithm
20:Knuth–Morris–Pratt algorithm
7:
3751:Trabb Pardo–Knuth algorithm
3492:Compressed pattern matching
3218:Approximate string matching
3200:
2875:Matiyasevich, Yuri (1973).
2598:is consulted for the index
2549:
1353:We consider the example of
10:
3860:
3834:String matching algorithms
3497:Longest common subsequence
3408:Needleman–Wunsch algorithm
3278:String-searching algorithm
2997:Introduction to Algorithms
2511:time complexity using the
1580:, and indeed this is also
1490:implies the corresponding
1466:We pass to the subsequent
1016:j ← j + 1
911:, which indicates that if
887:that fails when comparing
813:, but the next character,
170:string-searching algorithm
144:{\displaystyle \Theta (m)}
103:{\displaystyle \Theta (n)}
74:{\displaystyle \Theta (m)}
3793:Knuth's up-arrow notation
3770:
3762:Knuth's Simpath algorithm
3716:
3693:
3665:
3630:
3593:Computers and Typesetting
3570:
3507:Sequential pattern mining
3474:
3421:
3388:
3355:
3347:Commentz-Walter algorithm
3335:Multiple string searching
3334:
3276:
3268:Wagner–Fischer algorithm
3208:
2856:Матиясевич, Юрий (1971).
2769:SIAM Journal on Computing
1553:. So backtracking before
1478:. But instead of setting
1241:exists as a substring of
196:"a few weeks later" from
114:
44:
34:
24:
3517:String rewriting systems
3502:Longest common substring
3413:Smith–Waterman algorithm
3238:Gestalt pattern matching
2692:
1155:. Now, the loop ends if
3586:The Complexity of Songs
3451:Generalized suffix tree
3375:Thompson's construction
2958:10.1145/1240233.1240242
3621:Selected papers series
3403:Hirschberg's algorithm
2934:
2738:
2718:
2672:
2652:
2632:
2612:
2592:
2572:
2505:
2476:
2443:
2417:
2358:
2312:
2292:
1588:to find a segment for
1401:) has a proper suffix
1076:fails while comparing
982:k ← k + 1
978:j ← j + 1
536:S = ' '
410:characters that match
145:
104:
75:
3803:Quater-imaginary base
3258:Levenshtein automaton
3248:Jaro–Winkler distance
3154:July 7, 2023, at the
3062:Szpankowski, Wojciech
2983:Leiserson, Charles E.
2946:ACM Trans. Algorithms
2929:
2739:
2719:
2673:
2653:
2633:
2613:
2593:
2573:
2506:
2477:
2444:
2418:
2359:
2313:
2293:
1365:, we must discover a
638:giving a mismatch at
146:
105:
76:
3757:Dijkstra's algorithm
3695:Literate programming
3600:Concrete Mathematics
3306:Rabin–Karp algorithm
3263:Levenshtein distance
3144:Proof of correctness
3028:Crochemore, Maxime;
2728:
2708:
2662:
2642:
2622:
2602:
2582:
2562:
2504:{\displaystyle O(k)}
2486:
2475:{\displaystyle 2k-2}
2457:
2449:iterations in total.
2427:
2401:
2381:is always less than
2342:
2302:
2291:{\displaystyle O(k)}
2273:
2238:T ← cnd
1409:. Therefore, we set
1111:, so that the index
1107:and does not change
390:, it will increment
323:, and that the word
126:
85:
56:
3726:Knuth's Algorithm X
3461:Ternary search tree
3130:by Chu-Cheng Hsieh.
2442:{\displaystyle k-1}
2416:{\displaystyle k-1}
2357:{\displaystyle k-1}
2217:pos < length(W)
1329:initial segment of
572:ABCDAB ABCDABCDABDE
497:ABCDAB ABCDABCDABDE
288:is on the order of
244:. At each position
21:
3783:Knuth reward check
3755:Generalization of
3390:Sequence alignment
3357:Regular expression
2893:10.1007/BF01117471
2734:
2714:
2668:
2648:
2628:
2608:
2588:
2568:
2501:
2472:
2439:
2413:
2373:is initialized to
2354:
2308:
2288:
1557:is pointless, but
1005:k ← T
852:i:
848:W:
546:, we note that no
141:
100:
71:
19:
3844:1970 in computing
3821:
3820:
3530:
3529:
3522:String operations
2987:Rivest, Ronald L.
2827:978-0-444-10491-5
2737:{\displaystyle n}
2717:{\displaystyle m}
2683:Booth's algorithm
2671:{\displaystyle x}
2651:{\displaystyle x}
2631:{\displaystyle i}
2611:{\displaystyle i}
2591:{\displaystyle x}
2571:{\displaystyle x}
2318:is the length of
2311:{\displaystyle k}
2180:
2179:
1930:
1929:
1813:
1812:
1698:Another example:
1696:
1695:
1187:, then certainly
1050:is the length of
964:j < length(S)
717:) does not match
188:was conceived by
154:
153:
3851:
3557:
3550:
3543:
3534:
3533:
3487:Pattern matching
3441:Suffix automaton
3243:Hamming distance
3195:
3188:
3181:
3172:
3171:
3087:
3057:
3030:Rytter, Wojciech
3024:
3000:
2970:
2969:
2941:
2935:
2922:
2916:
2915:
2913:
2912:
2872:
2862:
2853:
2847:
2846:
2838:
2832:
2831:
2801:
2795:
2794:
2784:
2764:
2744:
2743:
2741:
2740:
2735:
2723:
2721:
2720:
2715:
2703:
2677:
2675:
2674:
2669:
2657:
2655:
2654:
2649:
2637:
2635:
2634:
2629:
2617:
2615:
2614:
2609:
2597:
2595:
2594:
2589:
2577:
2575:
2574:
2569:
2545:
2541:
2534:
2530:
2526:
2510:
2508:
2507:
2502:
2481:
2479:
2478:
2473:
2448:
2446:
2445:
2440:
2422:
2420:
2419:
2414:
2396:
2392:
2388:
2384:
2380:
2376:
2372:
2369:The inner loop:
2363:
2361:
2360:
2355:
2337:
2333:
2329:
2326:The outer loop:
2321:
2317:
2315:
2314:
2309:
2297:
2295:
2294:
2289:
2253:cnd ← T
2207:define variables
2101:
2022:
1940:
1935:
1934:
1896:
1860:
1823:
1818:
1817:
1779:
1743:
1706:
1701:
1700:
1668:
1638:
1607:
1602:
1601:
1595:
1591:
1587:
1583:
1579:
1575:
1568:
1564:
1560:
1556:
1552:
1548:
1544:
1540:
1536:
1532:
1528:
1524:
1520:
1513:
1509:
1505:
1501:
1497:
1493:
1489:
1485:
1481:
1477:
1473:
1469:
1462:
1455:
1451:
1447:
1443:
1439:
1435:
1419:
1412:
1408:
1404:
1400:
1396:
1392:
1388:
1384:
1380:
1376:
1372:
1364:
1360:
1356:
1340:
1336:
1332:
1324:
1320:
1316:
1312:
1300:
1284:
1280:
1276:
1272:
1268:
1264:
1260:
1256:
1252:
1248:
1244:
1240:
1236:
1232:
1228:
1224:
1198:
1190:
1182:
1178:
1174:
1170:
1158:
1154:
1150:
1146:
1142:
1138:
1134:
1130:
1126:
1122:
1118:
1114:
1110:
1106:
1095:
1091:
1087:
1083:
1079:
1075:
1071:
1067:
1053:
1031:
954:define variables
930:
926:
922:
914:
910:
906:
902:
898:
894:
890:
886:
882:
874:
862:
855:
851:
847:
844:
836:
832:
828:
824:
820:
816:
812:
805:
802:
798:
795:
791:
788:
785:
777:
773:
769:
762:
759:
755:
752:
748:
740:
736:
732:
728:
724:
720:
716:
712:
705:
702:
699:
695:
692:
689:
685:
682:
674:
670:
666:
662:
658:
654:
649:
645:
641:
637:
633:
629:
622:
619:
615:
612:
608:
605:
598:
594:
587:
584:
580:
577:
573:
565:
561:
557:
553:
549:
545:
541:
537:
533:
529:
525:
518:
515:
512:
508:
505:
502:
498:
495:
487:
483:
479:
471:
467:
461:
457:
453:
446:
443:= "ABCDABD" and
442:
425:
421:
417:
413:
401:
393:
389:
385:
362:
339:
326:
318:
314:
307:
303:
283:
275:
271:
267:
263:
259:
255:
251:
247:
243:
239:
228:
224:
220:
179:
175:
158:computer science
150:
148:
147:
142:
119:space complexity
109:
107:
106:
101:
81:preprocessing +
80:
78:
77:
72:
22:
18:
3859:
3858:
3854:
3853:
3852:
3850:
3849:
3848:
3824:
3823:
3822:
3817:
3798:Man or boy test
3766:
3712:
3689:
3680:Computer Modern
3661:
3626:
3607:Surreal Numbers
3566:
3561:
3531:
3526:
3470:
3417:
3384:
3370:Regular grammar
3351:
3330:
3311:Raita algorithm
3272:
3223:Bitap algorithm
3204:
3199:
3156:Wayback Machine
3107:sample C++ code
3094:
3076:
3046:
3013:
2991:Stein, Clifford
2974:
2973:
2942:
2938:
2923:
2919:
2910:
2908:
2860:
2854:
2850:
2839:
2835:
2828:
2802:
2798:
2791:10.1137/0206024
2765:
2758:
2753:
2748:
2747:
2729:
2726:
2725:
2709:
2706:
2705:
2704:
2700:
2695:
2663:
2660:
2659:
2643:
2640:
2639:
2623:
2620:
2619:
2603:
2600:
2599:
2583:
2580:
2579:
2563:
2560:
2559:
2552:
2543:
2539:
2532:
2528:
2524:
2521:
2487:
2484:
2483:
2458:
2455:
2454:
2428:
2425:
2424:
2402:
2399:
2398:
2394:
2390:
2386:
2382:
2378:
2374:
2370:
2343:
2340:
2339:
2335:
2331:
2327:
2319:
2303:
2300:
2299:
2274:
2271:
2270:
2267:
2262:
2185:
2099:
2020:
1938:
1894:
1858:
1821:
1777:
1741:
1704:
1666:
1636:
1605:
1593:
1589:
1585:
1581:
1577:
1573:
1566:
1562:
1558:
1554:
1550:
1546:
1542:
1538:
1534:
1530:
1529:, we still set
1526:
1522:
1518:
1511:
1507:
1503:
1499:
1495:
1491:
1487:
1483:
1479:
1475:
1471:
1467:
1460:
1453:
1449:
1445:
1441:
1437:
1433:
1417:
1410:
1406:
1402:
1398:
1394:
1390:
1386:
1382:
1378:
1374:
1370:
1362:
1358:
1354:
1351:
1341:, as discussed
1338:
1334:
1330:
1322:
1318:
1314:
1310:
1303:initial segment
1298:
1295:
1282:
1278:
1274:
1270:
1266:
1262:
1258:
1254:
1253:), we increase
1250:
1246:
1242:
1238:
1234:
1230:
1226:
1222:
1196:
1188:
1180:
1176:
1172:
1168:
1156:
1152:
1148:
1144:
1140:
1136:
1135:unchanged, for
1132:
1128:
1124:
1120:
1116:
1112:
1108:
1104:
1093:
1089:
1085:
1081:
1077:
1073:
1069:
1063:
1051:
1029:
1026:
1021:
928:
924:
920:
912:
908:
904:
900:
896:
892:
888:
884:
880:
872:
869:
860:
857:
856:
853:
849:
845:
842:
834:
830:
826:
822:
818:
814:
810:
807:
806:
803:
800:
796:
793:
789:
786:
783:
775:
771:
767:
764:
763:
760:
757:
753:
750:
746:
738:
734:
730:
726:
722:
718:
714:
710:
707:
706:
703:
700:
697:
693:
690:
687:
683:
680:
672:
668:
664:
660:
656:
652:
647:
643:
639:
635:
631:
627:
624:
623:
620:
617:
613:
610:
606:
603:
596:
592:
589:
588:
585:
582:
578:
575:
571:
563:
559:
555:
551:
547:
543:
539:
538:does not match
535:
531:
527:
523:
520:
519:
516:
513:
510:
506:
503:
500:
496:
493:
485:
484:and increments
481:
477:
469:
465:
459:
455:
451:
444:
440:
437:
432:
423:
419:
415:
411:
399:
391:
387:
386:= 999) because
383:
360:
337:
324:
316:
312:
305:
301:
292:comparisons or
281:
273:
269:
265:
261:
257:
253:
249:
245:
241:
237:
226:
222:
218:
215:
198:automata theory
190:James H. Morris
177:
173:
127:
124:
123:
86:
83:
82:
57:
54:
53:
17:
12:
11:
5:
3857:
3847:
3846:
3841:
3836:
3819:
3818:
3816:
3815:
3810:
3805:
3800:
3795:
3790:
3785:
3780:
3774:
3772:
3768:
3767:
3765:
3764:
3759:
3753:
3748:
3743:
3738:
3733:
3728:
3722:
3720:
3714:
3713:
3711:
3710:
3705:
3699:
3697:
3691:
3690:
3688:
3687:
3685:Concrete Roman
3682:
3677:
3671:
3669:
3663:
3662:
3660:
3659:
3653:
3647:
3642:
3636:
3634:
3628:
3627:
3625:
3624:
3617:
3610:
3603:
3596:
3589:
3582:
3574:
3572:
3568:
3567:
3560:
3559:
3552:
3545:
3537:
3528:
3527:
3525:
3524:
3519:
3514:
3509:
3504:
3499:
3494:
3489:
3484:
3478:
3476:
3472:
3471:
3469:
3468:
3463:
3458:
3453:
3448:
3443:
3438:
3433:
3427:
3425:
3423:Data structure
3419:
3418:
3416:
3415:
3410:
3405:
3400:
3394:
3392:
3386:
3385:
3383:
3382:
3377:
3372:
3367:
3361:
3359:
3353:
3352:
3350:
3349:
3344:
3338:
3336:
3332:
3331:
3329:
3328:
3323:
3318:
3316:Trigram search
3313:
3308:
3303:
3298:
3293:
3288:
3282:
3280:
3274:
3273:
3271:
3270:
3265:
3260:
3255:
3250:
3245:
3240:
3235:
3230:
3225:
3220:
3214:
3212:
3206:
3205:
3198:
3197:
3190:
3183:
3175:
3169:
3168:
3163:
3158:
3146:
3141:
3136:
3131:
3125:
3119:
3113:
3111:David Eppstein
3100:
3093:
3092:External links
3090:
3089:
3088:
3074:
3058:
3044:
3025:
3011:
2979:Cormen, Thomas
2972:
2971:
2936:
2917:
2867:(in Russian).
2848:
2833:
2826:
2796:
2782:10.1.1.93.8147
2775:(2): 323–350.
2755:
2754:
2752:
2749:
2746:
2745:
2733:
2713:
2697:
2696:
2694:
2691:
2667:
2647:
2627:
2607:
2587:
2567:
2551:
2548:
2520:
2517:
2513:Big O notation
2500:
2497:
2494:
2491:
2471:
2468:
2465:
2462:
2451:
2450:
2438:
2435:
2432:
2412:
2409:
2406:
2366:
2365:
2353:
2350:
2347:
2307:
2287:
2284:
2281:
2278:
2266:
2263:
2231:T ← T
2190:
2184:
2181:
2178:
2177:
2174:
2171:
2168:
2165:
2162:
2159:
2156:
2153:
2150:
2147:
2144:
2141:
2138:
2135:
2132:
2129:
2126:
2123:
2120:
2117:
2114:
2111:
2108:
2105:
2102:
2096:
2095:
2093:
2090:
2087:
2084:
2081:
2078:
2075:
2072:
2069:
2066:
2064:
2061:
2058:
2056:
2053:
2050:
2047:
2044:
2041:
2038:
2035:
2032:
2029:
2026:
2023:
2017:
2016:
2013:
2010:
2007:
2004:
2001:
1998:
1995:
1992:
1989:
1986:
1983:
1980:
1977:
1974:
1971:
1968:
1965:
1962:
1959:
1956:
1953:
1950:
1947:
1944:
1941:
1928:
1927:
1924:
1921:
1918:
1915:
1912:
1909:
1906:
1903:
1900:
1897:
1891:
1890:
1888:
1885:
1882:
1879:
1876:
1873:
1870:
1867:
1864:
1861:
1855:
1854:
1851:
1848:
1845:
1842:
1839:
1836:
1833:
1830:
1827:
1824:
1811:
1810:
1807:
1804:
1801:
1798:
1795:
1792:
1789:
1786:
1783:
1780:
1774:
1773:
1771:
1768:
1765:
1762:
1759:
1756:
1753:
1750:
1747:
1744:
1738:
1737:
1734:
1731:
1728:
1725:
1722:
1719:
1716:
1713:
1710:
1707:
1694:
1693:
1690:
1687:
1684:
1681:
1678:
1675:
1672:
1669:
1663:
1662:
1660:
1657:
1654:
1651:
1648:
1645:
1642:
1639:
1633:
1632:
1629:
1626:
1623:
1620:
1617:
1614:
1611:
1608:
1416:Continuing to
1350:
1347:
1294:
1291:
1281:is bounded by
1060:big-O notation
1025:
1022:
986:k = length(W)
937:
868:
865:
840:
839:
799:i:
792:W:
781:
780:
744:
743:
678:
677:
601:
600:
569:
568:
491:
490:
474:
473:
463:
436:
433:
431:
428:
214:
211:
152:
151:
140:
137:
134:
131:
121:
112:
111:
99:
96:
93:
90:
70:
67:
64:
61:
51:
42:
41:
36:
35:Data structure
32:
31:
26:
15:
9:
6:
4:
3:
2:
3856:
3845:
3842:
3840:
3837:
3835:
3832:
3831:
3829:
3814:
3811:
3809:
3806:
3804:
3801:
3799:
3796:
3794:
3791:
3789:
3786:
3784:
3781:
3779:
3778:Dancing Links
3776:
3775:
3773:
3769:
3763:
3760:
3758:
3754:
3752:
3749:
3747:
3744:
3742:
3741:Knuth shuffle
3739:
3737:
3734:
3732:
3729:
3727:
3724:
3723:
3721:
3719:
3715:
3709:
3706:
3704:
3701:
3700:
3698:
3696:
3692:
3686:
3683:
3681:
3678:
3676:
3673:
3672:
3670:
3668:
3664:
3657:
3654:
3652:
3648:
3646:
3643:
3641:
3638:
3637:
3635:
3633:
3629:
3623:
3622:
3618:
3616:
3615:
3611:
3609:
3608:
3604:
3602:
3601:
3597:
3595:
3594:
3590:
3587:
3583:
3581:
3580:
3576:
3575:
3573:
3569:
3565:
3558:
3553:
3551:
3546:
3544:
3539:
3538:
3535:
3523:
3520:
3518:
3515:
3513:
3510:
3508:
3505:
3503:
3500:
3498:
3495:
3493:
3490:
3488:
3485:
3483:
3480:
3479:
3477:
3473:
3467:
3464:
3462:
3459:
3457:
3454:
3452:
3449:
3447:
3444:
3442:
3439:
3437:
3434:
3432:
3429:
3428:
3426:
3424:
3420:
3414:
3411:
3409:
3406:
3404:
3401:
3399:
3396:
3395:
3393:
3391:
3387:
3381:
3378:
3376:
3373:
3371:
3368:
3366:
3363:
3362:
3360:
3358:
3354:
3348:
3345:
3343:
3340:
3339:
3337:
3333:
3327:
3324:
3322:
3319:
3317:
3314:
3312:
3309:
3307:
3304:
3302:
3299:
3297:
3294:
3292:
3289:
3287:
3284:
3283:
3281:
3279:
3275:
3269:
3266:
3264:
3261:
3259:
3256:
3254:
3251:
3249:
3246:
3244:
3241:
3239:
3236:
3234:
3233:Edit distance
3231:
3229:
3226:
3224:
3221:
3219:
3216:
3215:
3213:
3211:
3210:String metric
3207:
3203:
3196:
3191:
3189:
3184:
3182:
3177:
3176:
3173:
3167:
3164:
3162:
3159:
3157:
3153:
3150:
3147:
3145:
3142:
3140:
3137:
3135:
3132:
3129:
3126:
3123:
3120:
3117:
3114:
3112:
3108:
3104:
3101:
3099:
3096:
3095:
3085:
3081:
3077:
3075:0-471-24063-X
3071:
3067:
3063:
3059:
3055:
3051:
3047:
3045:981-02-4897-0
3041:
3037:
3036:
3031:
3026:
3022:
3018:
3014:
3012:0-262-03293-7
3008:
3004:
2999:
2998:
2992:
2988:
2984:
2980:
2976:
2975:
2967:
2963:
2959:
2955:
2951:
2947:
2940:
2933:
2927:
2921:
2906:
2902:
2898:
2894:
2890:
2886:
2882:
2878:
2870:
2866:
2859:
2852:
2844:
2837:
2829:
2823:
2819:
2815:
2811:
2807:
2800:
2792:
2788:
2783:
2778:
2774:
2770:
2763:
2761:
2756:
2731:
2711:
2702:
2698:
2690:
2688:
2684:
2680:
2665:
2645:
2625:
2605:
2585:
2565:
2557:
2547:
2536:
2516:
2514:
2495:
2489:
2469:
2466:
2463:
2460:
2436:
2433:
2430:
2410:
2407:
2404:
2368:
2367:
2351:
2348:
2345:
2325:
2324:
2323:
2305:
2282:
2276:
2260:
2256:
2252:
2249:
2245:
2241:
2237:
2234:
2230:
2227:
2223:
2220:
2216:
2212:
2208:
2204:
2200:
2196:
2193:
2189:
2175:
2172:
2169:
2166:
2163:
2160:
2157:
2154:
2151:
2148:
2145:
2142:
2139:
2136:
2133:
2130:
2127:
2124:
2121:
2118:
2115:
2112:
2109:
2106:
2103:
2098:
2097:
2094:
2091:
2088:
2085:
2082:
2079:
2076:
2073:
2070:
2067:
2065:
2062:
2059:
2057:
2054:
2051:
2048:
2045:
2042:
2039:
2036:
2033:
2030:
2027:
2024:
2019:
2018:
2014:
2011:
2008:
2005:
2002:
1999:
1996:
1993:
1990:
1987:
1984:
1981:
1978:
1975:
1972:
1969:
1966:
1963:
1960:
1957:
1954:
1951:
1948:
1945:
1942:
1937:
1936:
1933:
1925:
1922:
1919:
1916:
1913:
1910:
1907:
1904:
1901:
1898:
1893:
1892:
1889:
1886:
1883:
1880:
1877:
1874:
1871:
1868:
1865:
1862:
1857:
1856:
1852:
1849:
1846:
1843:
1840:
1837:
1834:
1831:
1828:
1825:
1820:
1819:
1816:
1808:
1805:
1802:
1799:
1796:
1793:
1790:
1787:
1784:
1781:
1776:
1775:
1772:
1769:
1766:
1763:
1760:
1757:
1754:
1751:
1748:
1745:
1740:
1739:
1735:
1732:
1729:
1726:
1723:
1720:
1717:
1714:
1711:
1708:
1703:
1702:
1699:
1691:
1688:
1685:
1682:
1679:
1676:
1673:
1670:
1665:
1664:
1661:
1658:
1655:
1652:
1649:
1646:
1643:
1640:
1635:
1634:
1630:
1627:
1624:
1621:
1618:
1615:
1612:
1609:
1604:
1603:
1600:
1597:
1570:
1515:
1464:
1457:
1431:
1430:proper prefix
1427:
1426:proper suffix
1423:
1414:
1368:
1367:proper suffix
1355:W = "ABCDABD"
1346:
1344:
1328:
1307:
1304:
1290:
1288:
1219:
1217:
1213:
1209:
1204:
1202:
1194:
1186:
1166:
1162:
1102:
1097:
1066:
1061:
1057:
1049:
1045:
1043:
1039:
1035:
1019:
1015:
1012:
1008:
1004:
1001:
997:
993:
989:
985:
981:
977:
974:
970:
967:
963:
959:
955:
951:
947:
943:
940:
936:
934:
918:
878:
864:
838:
779:
766:The match at
756:i:
749:W:
742:
676:
599:
567:
489:
464:
450:
449:
448:
430:KMP algorithm
427:
409:
405:
397:
380:
378:
374:
370:
366:
357:
355:
351:
347:
343:
334:
330:
322:
309:
299:
295:
291:
287:
277:
235:
230:
210:
207:
203:
202:Vaughan Pratt
200:. Morris and
199:
195:
191:
187:
182:
171:
167:
166:KMP algorithm
163:
159:
135:
122:
120:
117:
113:
94:
65:
52:
50:
47:
43:
40:
37:
33:
30:
29:String search
27:
23:
3839:Donald Knuth
3735:
3619:
3612:
3605:
3598:
3591:
3577:
3571:Publications
3564:Donald Knuth
3436:Suffix array
3342:Aho–Corasick
3300:
3253:Lee distance
3124:by H.W. Lang
3065:
3034:
2996:
2949:
2945:
2939:
2930:
2925:
2920:
2909:. Retrieved
2884:
2880:
2868:
2864:
2851:
2842:
2836:
2809:
2805:
2799:
2772:
2768:
2701:
2681:
2553:
2537:
2522:
2452:
2268:
2258:
2254:
2250:
2247:
2243:
2239:
2235:
2232:
2228:
2225:
2221:
2218:
2214:
2210:
2206:
2202:
2198:
2194:
2191:
2186:
1931:
1814:
1697:
1598:
1571:
1516:
1465:
1458:
1421:
1415:
1381:, so we set
1352:
1326:
1308:
1302:
1296:
1286:
1229:at position
1220:
1215:
1211:
1207:
1205:
1200:
1192:
1184:
1164:
1160:
1100:
1098:
1064:
1055:
1047:
1041:
1037:
1027:
1017:
1013:
1010:
1006:
1002:
999:
995:
991:
987:
983:
979:
975:
972:
968:
965:
961:
957:
953:
949:
945:
941:
938:
916:
875:, described
870:
858:
821:of the word
808:
765:
747:ABCDABCDABDE
708:
684:ABCDABCDABDE
671:(the prefix
625:
607:ABCDABCDABDE
590:
521:
475:
438:
407:
403:
395:
381:
376:
372:
368:
364:
358:
353:
349:
345:
341:
332:
328:
320:
310:
297:
293:
289:
285:
278:
268:at position
231:
216:
206:Matiyasevich
194:Donald Knuth
183:
165:
161:
155:
3788:Knuth Prize
3446:Suffix tree
2812:: 189–195.
2364:iterations.
2213:T ← -1
1521:, which is
1494:character,
1428:which is a
1361:. To find
1245:at p, then
960:nP ← 0
696:i:
686:W:
234:brute-force
49:performance
3828:Categories
3718:Algorithms
3084:0968.68205
3054:1078.68151
3021:1047.68161
2911:2017-07-04
2871:: 104–114.
2751:References
2332:pos < k
1385:. To find
1092:, so that
1034:complexity
1020:k ← k + 1
942:kmp_search
933:pseudocode
903:(that is,
284:of length
221:in string
213:Background
116:Worst-case
46:Worst-case
3675:AMS Euler
2952:(2): 19.
2901:121919479
2887:: 64–70.
2777:CiteSeerX
2556:real-time
2467:−
2434:−
2408:−
2349:−
2195:kmp_table
2192:algorithm
1576:would be
1177:m ≤ m + i
1009:k < 0
939:algorithm
921:m + i - T
919:at index
897:m + i - T
186:algorithm
130:Θ
89:Θ
60:Θ
3645:Metafont
3632:Software
3152:Archived
3064:(2001).
3032:(2003).
2928: :
2905:Archived
2550:Variants
2533:O(n + k)
2298:, where
2242:cnd ≥ 0
1565:, hence
1448:and not
1265:, where
1151:, hence
1094:T < i
1054:and the
1046:, where
811:"ABCDAB"
737:, reset
723:' '
632:"ABCDAB"
110:matching
3808:-yllion
3649:MIXAL (
3512:Sorting
3482:Parsing
3202:Strings
2966:8409826
2932:memory.
2391:cnd ≥ 0
1574:W = 'A'
1561:may be
1551:S ≠ 'B'
1500:S ≠ 'A'
854:0123456
850:ABCDABD
843:ABCDABD
616:i:
609:W:
540:W = 'D'
462:begins,
352:⋅
327:is 999
168:) is a
3082:
3072:
3052:
3042:
3019:
3009:
3005:–931.
2964:
2899:
2824:
2779:
2334:, and
2246:W ≠ W
2224:W = W
2203:output
2197::
1535:T = -1
1512:T = -1
1359:T = -1
1339:T = -1
1327:proper
1175:, and
971:W = S
950:output
944::
909:T = -1
827:m = 15
801:012345
794:ABCDAB
784:ABCDAB
772:m = 11
761:123456
754:BCDABD
735:m = 10
634:until
626:Here,
618:012345
611:ABCDAB
604:ABCDAB
586:123456
581:i:
579:BCDABD
574:W:
262:S =? W
250:S =? W
160:, the
39:String
3771:Other
3667:Fonts
3475:Other
3431:DAFSA
3398:BLAST
2962:S2CID
2897:S2CID
2861:(PDF)
2693:Notes
2385:, so
2240:while
2215:while
2199:input
1594:T = 2
1567:T = 0
1531:T = 0
1484:W = W
1480:T = 0
1461:T = 0
1454:T = m
1450:T = 1
1446:T = 0
1411:T = 0
1383:T = 0
1343:below
1273:with
1263:i = T
1259:W ≠ S
1251:W = S
1247:W = S
1237:. If
1197:m + i
1189:m + i
1179:: if
1169:m + i
1157:m + i
1141:i - T
1139:gets
1133:m + i
1121:i - T
1113:m + i
1065:while
962:while
946:input
917:begin
877:below
835:i = 2
790:DABDE
776:i = 0
739:i = 0
663:(the
657:i = 2
653:m = 8
636:i = 6
597:i = 0
593:m = 4
564:i = 0
560:m = 3
480:with
388:S ≠ W
25:Class
3708:CWEB
3656:MMIX
3466:Trie
3456:Rope
3105:and
3070:ISBN
3040:ISBN
3007:ISBN
2822:ISBN
2529:O(n)
2527:and
2525:O(k)
2233:else
2226:then
1399:"AB"
1233:and
1225:and
1011:then
1000:else
988:then
973:then
831:"AB"
774:and
768:m=10
704:3456
694:DABD
673:"AB"
665:"AB"
648:"AB"
642:and
595:and
562:and
184:The
164:(or
3703:WEB
3651:MIX
3640:TeX
3109:by
3080:Zbl
3050:Zbl
3017:Zbl
3003:923
2954:doi
2889:doi
2814:doi
2787:doi
2542:or
2395:cnd
2387:cnd
2383:cnd
2371:cnd
2336:pos
2328:pos
2259:let
2255:let
2251:let
2244:and
2236:let
2229:let
2211:let
2149:-1
2125:-1
2104:-1
2015:24
2012:23
2009:22
2006:21
2003:20
2000:19
1997:18
1994:17
1991:16
1988:15
1985:14
1982:13
1979:12
1976:11
1973:10
1970:09
1967:08
1964:07
1961:06
1958:05
1955:04
1952:03
1949:02
1946:01
1943:00
1923:-1
1917:-1
1911:-1
1905:-1
1899:-1
1800:-1
1794:-1
1788:-1
1782:-1
1683:-1
1671:-1
1578:'B'
1563:'A'
1527:'A'
1523:'B'
1472:'A'
1422:all
1403:"B"
1379:"A"
1371:"A"
1369:of
1218:).
1171:or
1123:to
1086:S)]
1080:to
1058:is
1018:let
1014:let
1003:let
996:let
992:let
980:let
976:let
958:let
899:in
891:to
819:'D'
815:'C'
721:(a
715:'C'
713:(a
675:).
548:'A'
517:456
511:012
509:i:
507:ABD
501:ABC
499:W:
494:ABC
426:).
379:).
356:).
340:is
156:In
3830::
3078:.
3048:.
3015:.
2989:;
2985:;
2981:;
2960:.
2948:.
2903:.
2895:.
2883:.
2879:.
2869:20
2863:.
2820:.
2810:74
2808:.
2785:.
2771:.
2759:^
2554:A
2546:.
2535:.
2515:.
2322:.
2248:do
2222:if
2219:do
2176:0
2173:0
2170:0
2167:0
2164:0
2161:0
2158:3
2155:0
2152:0
2146:0
2143:0
2140:0
2137:0
2134:0
2131:2
2128:0
2122:0
2119:0
2116:0
2113:0
2110:0
2107:0
2092:E
2089:T
2086:U
2083:H
2080:C
2077:A
2074:R
2071:A
2068:P
2063:N
2060:I
2055:E
2052:T
2049:A
2046:P
2043:I
2040:C
2037:I
2034:T
2031:R
2028:A
2025:P
1926:3
1920:3
1914:0
1908:1
1902:0
1887:A
1884:B
1881:A
1878:B
1875:A
1872:C
1869:A
1866:B
1863:A
1853:9
1850:8
1847:7
1844:6
1841:5
1838:4
1835:3
1832:2
1829:1
1826:0
1809:0
1806:2
1803:3
1797:0
1791:1
1785:0
1770:C
1767:B
1764:A
1761:B
1758:A
1755:C
1752:A
1749:B
1746:A
1736:9
1733:8
1730:7
1727:6
1724:5
1721:4
1718:3
1715:2
1712:1
1709:0
1692:0
1689:2
1686:0
1680:0
1677:0
1674:0
1659:D
1656:B
1653:A
1650:D
1647:C
1644:B
1641:A
1631:7
1628:6
1625:5
1622:4
1619:3
1616:2
1613:1
1610:0
1596:.
1569:.
1549:,
1537:.
1514:.
1470:,
1463:.
1413:.
1393:-
1345:.
1289:.
1271:W]
1199:=
1191:≥
1183:=
1159:=
1096:.
1007:if
984:if
969:if
966:do
929:W]
863:.
778:.
741:.
733::
698:01
688:AB
681:AB
566:.
363:,
229:.
3658:)
3588:"
3584:"
3556:e
3549:t
3542:v
3194:e
3187:t
3180:v
3086:.
3056:.
3023:.
2968:.
2956::
2950:3
2914:.
2891::
2885:1
2830:.
2816::
2793:.
2789::
2773:6
2732:n
2712:m
2666:x
2646:x
2626:i
2606:i
2586:x
2566:x
2544:S
2540:W
2499:)
2496:k
2493:(
2490:O
2470:2
2464:k
2461:2
2437:1
2431:k
2411:1
2405:k
2379:T
2375:0
2352:1
2346:k
2320:W
2306:k
2286:)
2283:k
2280:(
2277:O
2100:T
2021:W
1939:i
1895:T
1859:W
1822:i
1778:T
1742:W
1705:i
1667:T
1637:W
1606:i
1590:W
1586:W
1582:W
1559:S
1555:W
1547:S
1543:W
1539:W
1519:W
1508:W
1504:S
1496:S
1492:S
1488:T
1476:W
1468:W
1442:W
1438:W
1434:W
1418:T
1407:W
1397:(
1395:W
1391:W
1387:T
1375:W
1363:T
1335:W
1331:W
1323:T
1319:W
1315:W
1311:W
1299:S
1287:n
1283:i
1279:i
1275:S
1267:T
1255:i
1243:S
1239:W
1235:p
1231:i
1227:S
1223:W
1216:n
1214:(
1212:O
1208:n
1201:n
1193:n
1185:n
1181:m
1173:m
1165:n
1161:n
1149:i
1145:T
1137:m
1129:m
1125:m
1117:S
1109:m
1105:i
1101:n
1090:m
1082:W
1078:S
1074:S
1070:T
1056:O
1052:S
1048:n
1044:)
1042:n
1040:(
1038:O
1030:T
925:T
913:W
905:T
901:S
893:W
889:S
885:S
881:T
873:T
861:S
846:E
823:W
804:6
797:D
787:C
758:0
751:A
731:S
727:W
719:S
711:W
701:2
691:C
669:W
661:S
644:S
640:W
628:i
621:6
614:D
583:0
576:A
556:W
552:S
544:S
532:i
528:S
524:W
514:3
504:D
486:i
482:W
478:S
472:.
470:W
466:i
460:W
456:S
452:m
445:S
441:W
424:i
420:m
416:i
412:W
408:A
404:A
400:m
396:A
392:m
384:i
377:n
375:(
373:O
369:k
367:(
365:O
361:W
354:n
350:k
348:(
346:O
342:k
338:W
333:B
329:A
325:W
321:A
317:S
313:m
306:W
302:S
298:n
296:(
294:Θ
290:n
286:n
282:S
274:m
270:m
266:W
258:W
254:i
246:m
242:S
238:m
227:W
223:S
219:m
178:S
174:W
139:)
136:m
133:(
98:)
95:n
92:(
69:)
66:m
63:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.