String-searching algorithm: Revision history

View logs for this page (view filter log)

Filter revisionsshowhide To date:Tag filter:Invert selection

External tools:

For any version listed below, click on its date to view it. For more help, see Help:Page history and Help:Edit summary. (cur) = difference from current version, (prev) = difference from preceding version, m = minor edit, → = section edit, ← = automatic edit summary

(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)

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

cur prev 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
cur prev 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

cur prev 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

cur prev 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

cur prev 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

cur prev 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
cur prev 13:0213:02, 24 January 2024 190.96.105.113 talk 18,483 bytes +1 No edit summary undo Tag: Reverted
cur prev 13:0113:01, 24 January 2024 190.96.105.113 talk 18,482 bytes −1 No edit summary undo Tag: Reverted
cur prev 13:0013:00, 24 January 2024 190.96.105.113 talk 18,483 bytes −1 →Overview undo Tag: Reverted

29 December 2023

cur prev 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

cur prev 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

cur prev 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

cur prev 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
cur prev 17:1517:15, 7 October 2023 98.240.149.164 talk 18,742 bytes +73 →Stubs undo Tags: Reverted Visual edit
cur prev 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
cur prev 17:1417:14, 7 October 2023 98.240.149.164 talk 18,673 bytes +33 →Overview undo Tags: Reverted Visual edit

6 October 2023

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

24 September 2023

cur prev 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

cur prev 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 Misplaced Pages:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox2 | #UCB_webform_linked 1952/2384 undo

8 April 2023

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

16 March 2023

cur prev 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

22 October 2022

cur prev 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

cur prev 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
cur prev 10:3410:34, 13 October 2022 37.34.248.21 talk 17,658 bytes −900 →Overview undo Tag: Reverted

10 May 2022

cur prev 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

cur prev 10:3510:35, 22 March 2022 Nicoonoclaste talk contribs 17,202 bytes −12 →Single-pattern algorithms undo Tag: 2017 wikitext editor
cur prev 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
cur prev 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
cur prev 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
cur prev 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
cur prev 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
cur prev 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
cur prev 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

cur prev 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

cur prev 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

cur prev 22:2622:26, 2 January 2022 Sorisos talk contribs m 15,948 bytes +2 →Finite-state-automaton-based search: formulation used "we" undo
cur prev 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

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

4 October 2021

cur prev 01:2701:27, 4 October 2021 Aamini11 talk contribs 15,937 bytes +6 Undid revision 1048056351 by Aamini11 (talk) undo Tag: Undo
cur prev 00:5900:59, 4 October 2021 Aamini11 talk contribs 15,931 bytes −6 Θ((n-m)m) = Θ(mn). Having it listed is Θ(mn) would be bettter since it's a more simplified version of the previous expression. It's also more consistent since other time complexities in the table are listed as O(mn) instead of O(m*(m-n)), even though they technically could be. The full wiki article for the Rabin–Karp algorithm also states "its worst-case time complexity is the product of the two lengths" undo Tag: Reverted

25 August 2021

cur prev 04:3404:34, 25 August 2021 GünniX talk contribs 15,937 bytes −34 Undid revision 1040114420 by 2603:8090:1440:719B:FDAF:D89E:F06F:AA3B (talk) undo Tag: Undo

22 August 2021

cur prev 18:2218:22, 22 August 2021 2603:8090:1440:719b:fdaf:d89e:f06f:aa3b talk 15,971 bytes +34 →Overview undo Tag: Reverted

7 August 2021

cur prev 04:3004:30, 7 August 2021 Rdp060707 talk contribs m 15,937 bytes −8 Reverted edits by 2409:4064:258D:ECEC:0:0:26C3:F8B1 (talk) to last revision by SunDawn: nonconstructive edits undo Tags: Rollback SWViewer [1.4]
cur prev 04:3004:30, 7 August 2021 2409:4064:258d:ecec::26c3:f8b1 talk 15,945 bytes +8 No edit summary undo Tags: Reverted Mobile edit Mobile web edit