String-searching algorithm: Revision history

23 April 2025

• curprev 20:4120:41, 23 April 2025 OatPowered talk contribs m 18,458 bytes +76 →Classification by the use of preprocessing programs: Fix VLDB cite, update URL, add all authors and wikilink undo
• curprev 04:4704:47, 23 April 2025 HMSLavender talk contribs m 18,382 bytes +3,077 Reverted edits by 220.244.208.194 (talk) (AV) undo Tags: AntiVandal Rollback
• curprev 04:4704:47, 23 April 2025 220.244.208.194 talk 15,305 bytes −3,077 wvhdioooo undo Tag: Reverted

18 March 2025

• curprev 21:2921:29, 18 March 2025 MrOllie talk contribs 18,382 bytes −342 Reverted 1 edit by Jerzy.Respondek (talk): Rv citespam undo Tags: Twinkle Undo
• curprev 21:2821:28, 18 March 2025 Jerzy.Respondek talk contribs m 18,724 bytes +342 No edit summary undo Tag: Reverted

20 December 2024

• curprev 13:5813:58, 20 December 2024 Stevebroshar talk contribs 18,382 bytes −113 the target need not be larger (although probably won't find if it's smaller); singular reads better than plural undo

25 November 2024

• curprev 04:2304:23, 25 November 2024 ClueBot NG talk contribs m 18,495 bytes −6 Reverting possible vandalism by 113.161.109.242 to version by 2A0D:6FC2:5E30:9A00:71BB:FAF7:C2A:B6B2. Report False Positive? Thanks, ClueBot NG. (4360169) (Bot) undo Tag: Rollback
• curprev 04:2304:23, 25 November 2024 113.161.109.242 talk 18,501 bytes +6 aaa undo Tags: Reverted possible vandalism Visual edit

20 September 2024

• curprev 09:3209:32, 20 September 2024 2a0d:6fc2:5e30:9a00:71bb:faf7:c2a:b6b2 talk 18,495 bytes −1 →Single-pattern algorithms undo Tag: Visual edit

7 April 2024

• curprev 14:0114:01, 7 April 2024 ReiniUrban talk contribs 18,496 bytes +12 →Classification by matching strategies: Add Vectorized (eg. the current best EPSM) as other strategy undo Tags: Mobile edit Mobile web edit Advanced mobile edit

27 January 2024

• curprev 18:4218:42, 27 January 2024 2601:540:ca80:5fb0:9dd4:d34:8a4f:f5be talk 18,484 bytes 0 change link undo

24 January 2024

• curprev 13:0913:09, 24 January 2024 Broc talk contribs 18,484 bytes +1 Reverted 3 edits by 190.96.105.113 (talk) undo Tags: Twinkle Undo
• curprev 13:0213:02, 24 January 2024 190.96.105.113 talk 18,483 bytes +1 No edit summary undo Tag: Reverted
• curprev 13:0113:01, 24 January 2024 190.96.105.113 talk 18,482 bytes −1 No edit summary undo Tag: Reverted
• curprev 13:0013:00, 24 January 2024 190.96.105.113 talk 18,483 bytes −1 →Overview undo Tag: Reverted

29 December 2023

• curprev 07:2107:21, 29 December 2023 Pcordes talk contribs 18,484 bytes +25 →Single-pattern algorithms: As discussed earlier in the page, the average case for naive searching is Θ(n+m), when potential matches are rejected in O(1), not scaling with the total length of the needle. (I might have said "typical" instead of "average", but for consistency with the other entry let's say average) undo

27 December 2023

• curprev 03:2603:26, 27 December 2023 Citation bot talk contribs 18,459 bytes −315 Removed proxy/dead URL that duplicated identifier. Removed access-date with no URL. Removed parameters. | Use this bot. Report bugs. | #UCB_CommandLine undo

25 October 2023

• curprev 22:4522:45, 25 October 2023 InternetArchiveBot talk contribs 18,774 bytes +134 Rescuing 1 sources and tagging 0 as dead.) #IABot (v2.0.9.5) (AManWithNoPlan - 15897 undo

7 October 2023

• curprev 17:1617:16, 7 October 2023 AntiDionysius talk contribs m 18,640 bytes −102 Reverted 3 edits by 98.240.149.164 (talk) to last revision by Duckypotato undo Tags: Twinkle Undo
• curprev 17:1517:15, 7 October 2023 98.240.149.164 talk 18,742 bytes +73 →Stubs undo Tags: Reverted Visual edit
• curprev 17:1417:14, 7 October 2023 98.240.149.164 talk 18,669 bytes −4 →Finite-state-automaton-based search undo Tags: Reverted Visual edit
• curprev 17:1417:14, 7 October 2023 98.240.149.164 talk 18,673 bytes +33 →Overview undo Tags: Reverted Visual edit

6 October 2023

• curprev 16:0116:01, 6 October 2023 Duckypotato talk contribs m 18,640 bytes +2 grammar undo

24 September 2023

• curprev 18:1818:18, 24 September 2023 Citation bot talk contribs 18,638 bytes +61 Alter: title, template type. Add: publisher, chapter-url, chapter, doi-access. Removed or converted URL. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | #UCB_CommandLine undo

25 July 2023

• curprev 19:4319:43, 25 July 2023 Citation bot talk contribs 18,577 bytes +5 Alter: title, template type. Add: chapter-url, chapter. Removed or converted URL. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox2 | #UCB_webform_linked 1952/2384 undo

8 April 2023

• curprev 21:4121:41, 8 April 2023 Skyerise talk contribs 18,572 bytes +1 →Naive string search: 's -> is undo

16 March 2023

• curprev 23:2623:26, 16 March 2023 LachlanA talk contribs 18,571 bytes +5 →Single-pattern algorithms: two-way has space complexity log(m). Saying "O(1) because string lengths are bounded in practice" makes O(.) notation useless. undo

3 February 2023

• curprev 02:1402:14, 3 February 2023 ShelfSkewed talk contribs 18,566 bytes −11 →Single-pattern algorithms: dab link undo

19 January 2023

• curprev 20:2720:27, 19 January 2023 Mandarax talk contribs m 18,577 bytes 0 Correct punctuation undo Tag: AWB

22 December 2022

• curprev 17:4817:48, 22 December 2022 Frap talk contribs m 18,577 bytes −7 No edit summary undo

16 November 2022

• curprev 17:5917:59, 16 November 2022 Meno25 talk contribs 18,584 bytes −14 →Algorithms using a finite set of patterns undo
• curprev 17:5817:58, 16 November 2022 Meno25 talk contribs 18,598 bytes +8 →Algorithms using a finite set of patterns undo

22 October 2022

• curprev 22:2922:29, 22 October 2022 37.19.108.190 talk 18,590 bytes +32 BNDM algorithm's matching complexity is not O(n), it's the same as for the Boyer-Moore - Omega(n/m) at best, O(n*m) at worst. https://users.dcc.uchile.cl/~gnavarro/ps/cpm98.pdf undo

13 October 2022

• curprev 13:4813:48, 13 October 2022 Dirkbb talk contribs m 18,558 bytes +900 Reverted 1 edit by 37.34.248.21 (talk) to last revision by Smasongarrison undo Tags: Twinkle Undo Disambiguation links added
• curprev 10:3410:34, 13 October 2022 37.34.248.21 talk 17,658 bytes −900 →Overview undo Tag: Reverted

10 May 2022

• curprev 03:0203:02, 10 May 2022 Smasongarrison talk contribs 18,558 bytes +1,356 Rescuing 7 sources and tagging 0 as dead.) #IABot (v2.0.8.7 undo Tag: IABotManagementConsole [1.2]

22 March 2022

• curprev 10:3510:35, 22 March 2022 Nicoonoclaste talk contribs 17,202 bytes −12 →Single-pattern algorithms undo Tag: 2017 wikitext editor
• curprev 10:2410:24, 22 March 2022 Nicoonoclaste talk contribs m 17,214 bytes +85 →Single-pattern algorithms: 2-way algorithm: ref. needed on extensions handling fuzzy search and regexps undo Tag: 2017 wikitext editor
• curprev 07:5807:58, 22 March 2022 Nicoonoclaste talk contribs m 17,129 bytes +310 →Single-pattern algorithms: Mention that the 2-way algorithm is also used by musl, add supporting refs, clarify they are both C standard libraries undo Tag: 2017 wikitext editor
• curprev 07:5007:50, 22 March 2022 Nicoonoclaste talk contribs 16,819 bytes +13 →Single-pattern algorithms: Rework the “matching time” section undo Tag: 2017 wikitext editor
• curprev 07:4707:47, 22 March 2022 Nicoonoclaste talk contribs m 16,806 bytes +32 →Single-pattern algorithms: Link a page explaining what “DAWG” is in BNDM. undo Tags: 2017 wikitext editor Disambiguation links added
• curprev 07:4207:42, 22 March 2022 Nicoonoclaste talk contribs m 16,774 bytes +340 →Single-pattern algorithms: Rework the “algorithm name” column undo Tag: 2017 wikitext editor
• curprev 07:2907:29, 22 March 2022 Nicoonoclaste talk contribs 16,434 bytes −159 →Single-pattern algorithms: Remove misclassified algorithms: bitap is for approximate string matching; the FM-index is a substring index for full-text search (i.e. it is the searchable text that is preprocessed/indexed, not the pattern to be searched) undo Tag: 2017 wikitext editor
• curprev 07:1507:15, 22 March 2022 Nicoonoclaste talk contribs 16,593 bytes −469 →Single-pattern algorithms: Remove the “optimized naïve search” : changing the constant factor isn't a meaningful difference in asymptotic complexity, nor is the (vectorisation) optimization in question a new algorithm undo Tag: 2017 wikitext editor

19 March 2022

• curprev 14:1514:15, 19 March 2022 Nicoonoclaste talk contribs 17,062 bytes +1,190 →Algorithms using a finite set of patterns: Remove Rabin-Karp (misclassified, single-pattern algorithm), rework the section as a table, add asymptotic complexities undo Tag: 2017 wikitext editor

3 February 2022

• curprev 03:0003:00, 3 February 2022 2600:1700:87d0:1210:4d89:7f75:6d0b:27a8 talk 15,872 bytes −76 →Examples of search algorithms undo

2 January 2022

• curprev 22:2622:26, 2 January 2022 Sorisos talk contribs m 15,948 bytes +2 →Finite-state-automaton-based search: formulation used "we" undo
• curprev 22:2322:23, 2 January 2022 Sorisos talk contribs m 15,946 bytes −1 →Naïve string search: had funny 'i' character undo

10 November 2021

• curprev 20:5120:51, 10 November 2021 Frap talk contribs m 15,947 bytes +10 →Classification by matching strategies undo

4 October 2021

• curprev 01:2701:27, 4 October 2021 Aamini11 talk contribs 15,937 bytes +6 Undid revision 1048056351 by Aamini11 (talk) undo Tag: Undo