Knuth–Morris–Pratt algorithm: Revision history

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

curprev 22:3022:30, 20 September 2024 177.9.76.226 talk 33,988 bytes +1 Changed the Big O notation to Theta notation because it is talking about the expected/average performance, not the worst case (which is discussed below). undo

curprev 06:3506:35, 28 April 2024 Goodmans238 talk contribs 33,988 bytes +197 Rescuing 1 sources and tagging 0 as dead.) #IABot (v2.0.9.5 undo Tag: IABotManagementConsole [1.3]

curprev 15:5015:50, 18 April 2024 MrOllie talk contribs 33,791 bytes −434 rm someone's personal site per WP:EL undo

curprev 18:5418:54, 17 September 2023 Timy2shoes talk contribs m 34,121 bytes +33 Incorrect chance of a random match. Didn’t take into account that there are 26 possible matches. undo Tags: Visual edit Mobile edit Mobile web edit

curprev 05:3505:35, 30 August 2023 David Eppstein talk contribs 34,088 bytes +13 Undid revision 1172922978 by 202.3.77.209 (talk) partial removal of relevant text undo Tag: Undo
curprev 05:2505:25, 30 August 2023 202.3.77.209 talk 34,075 bytes −13 No edit summary undo Tag: Reverted

curprev 17:4617:46, 27 June 2023 David Eppstein talk contribs 34,087 bytes −129 Undid revision 1162159296 by 42.110.140.44 (talk) should go on the talk page undo Tag: Undo
curprev 10:0610:06, 27 June 2023 42.110.140.44 talk 34,216 bytes +129 →Description of pseudocode for the search algorithm: Requested correction of variable-names to be consistent between pseudo-code & explanation. undo Tags: Reverted Mobile edit Mobile web edit

curprev 15:0015:00, 18 October 2022 Aniroy1986 talk contribs 34,071 bytes +145 →External links: KMP is an advanced algorithm. I wanted to share a link to an article which explains the search time complexity of KMP with concrete examples & detailed steps. It should be helpful to new learners. undo Tag: Visual edit

curprev 07:1907:19, 14 November 2021 Citation bot talk contribs 33,935 bytes +39 Add: s2cid. | Use this bot. Report bugs. | Suggested by Abductive | #UCB_toolbar undo

curprev 07:3507:35, 29 June 2021 Madeyedexter talk contribs 33,393 bytes +105 No edit summary undo Tags: Mobile edit Mobile app edit Android app edit

curprev 14:0114:01, 9 June 2021 2601:41:4200:9360:dc25:6a04:1ea3:2e34 talk 33,288 bytes −5 thus is confusing. the space complexity W is not that because of the time complexity being W it is that because the array is size W undo

curprev 04:5204:52, 10 November 2020 David Eppstein talk contribs 33,305 bytes +408 Undid revision 987940673 by 216.106.94.95 (talk) regexp matching is not linear in the size of the pattern with technology available at that time undo Tag: Undo
curprev 03:4603:46, 10 November 2020 216.106.94.95 talk 32,897 bytes −408 Removed line claiming this was the first linear-time text matching algorithm. Regular expression matching dates from 1951 mathematically and several years prior to this in implementations other than KMP. It runs in linear time. The cited article attached to this claim was also removed, given that it totally failed to support the incorrect statement. undo Tags: Reverted references removed