Talk:Commentz-Walter algorithm - Revision history

Cewbot: Maintain {{WPBS}} and vital articles: 1 WikiProject template. Create {{WPBS}}.

2024-01-30T21:21:00Z

Maintain {{WPBS}} and vital articles: 1 WikiProject template. Create {{WPBS}}.

← Previous revision		Revision as of 21:21, 30 January 2024
Line 1:		Line 1:
			{{WikiProject banner shell\|
	{{WikiProject Computer science}}		{{WikiProject Computer science}}
			}}

	== Asymptotic Runtime ==		== Asymptotic Runtime ==

SineBot: Signing comment by Azarzosa - "added usernames of university editors"

2022-05-03T23:19:48Z

Signing comment by Azarzosa - "added usernames of university editors"

← Previous revision		Revision as of 23:19, 3 May 2022
Line 10:		Line 10:
	- azarzosa		- azarzosa
	- LeafThief		- LeafThief
			- birdybutt <!-- Template:Unsigned --><span class="autosigned" style="font-size:85%;">— Preceding [[Wikipedia:Signatures\|unsigned]] comment added by [[User:Azarzosa\|Azarzosa]] ([[User talk:Azarzosa#top\|talk]] • [[Special:Contributions/Azarzosa\|contribs]]) 23:18, 3 May 2022 (UTC)</span> <!--Autosigned by SineBot-->
	- birdybutt

Azarzosa: added usernames of university editors

2022-05-03T23:18:41Z

added usernames of university editors

← Previous revision		Revision as of 23:18, 3 May 2022
Line 5:		Line 5:
	Watson's thesis (referenced), Algorithm 4.18 is given as a generalized precursor to CW, and remark 4.20 gives its runtime as O(S*P) for text length S and max pattern length P. The final derivation of CW (Section 4.4.5) does not give a runtime. Section 13.1 claims "All of the algorithms [including CW-NORM, normal Commentz-Walter]... have worst-case running time linear in the		Watson's thesis (referenced), Algorithm 4.18 is given as a generalized precursor to CW, and remark 4.20 gives its runtime as O(S*P) for text length S and max pattern length P. The final derivation of CW (Section 4.4.5) does not give a runtime. Section 13.1 claims "All of the algorithms [including CW-NORM, normal Commentz-Walter]... have worst-case running time linear in the
	length of the input string. ...the running time of... CW-NORM depends (linearly...) upon the length of the shortest keyword in the keyword set." Additionally, in Section 5.1: "Although the Knuth-Morris-Pratt and Aho-Corasick algorithms have better worst-case running time than the Boyer-Moore and Commentz-Walter algorithms (respectively), the latter two algorithms are known to be extremely efficient in practice." <small><span class="autosigned">— Preceding [[Wikipedia:Signatures\|unsigned]] comment added by [[User:Doctor J\|Doctor J]] ([[User talk:Doctor J\|talk]] • [[Special:Contributions/Doctor J\|contribs]]) 22:27, 15 February 2012 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->		length of the input string. ...the running time of... CW-NORM depends (linearly...) upon the length of the shortest keyword in the keyword set." Additionally, in Section 5.1: "Although the Knuth-Morris-Pratt and Aho-Corasick algorithms have better worst-case running time than the Boyer-Moore and Commentz-Walter algorithms (respectively), the latter two algorithms are known to be extremely efficient in practice." <small><span class="autosigned">— Preceding [[Wikipedia:Signatures\|unsigned]] comment added by [[User:Doctor J\|Doctor J]] ([[User talk:Doctor J\|talk]] • [[Special:Contributions/Doctor J\|contribs]]) 22:27, 15 February 2012 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->


			We are editing this page as part of a university assignment, these are our usernames:
			- azarzosa
			- LeafThief
			- birdybutt

SineBot: Signing comment by Doctor J - "/* Asymptotic Runtime */ new section"

2012-02-15T22:28:17Z

Signing comment by Doctor J - "Asymptotic Runtime: new section"

← Previous revision		Revision as of 22:28, 15 February 2012
Line 4:		Line 4:

	Watson's thesis (referenced), Algorithm 4.18 is given as a generalized precursor to CW, and remark 4.20 gives its runtime as O(S*P) for text length S and max pattern length P. The final derivation of CW (Section 4.4.5) does not give a runtime. Section 13.1 claims "All of the algorithms [including CW-NORM, normal Commentz-Walter]... have worst-case running time linear in the		Watson's thesis (referenced), Algorithm 4.18 is given as a generalized precursor to CW, and remark 4.20 gives its runtime as O(S*P) for text length S and max pattern length P. The final derivation of CW (Section 4.4.5) does not give a runtime. Section 13.1 claims "All of the algorithms [including CW-NORM, normal Commentz-Walter]... have worst-case running time linear in the
	length of the input string. ...the running time of... CW-NORM depends (linearly...) upon the length of the shortest keyword in the keyword set." Additionally, in Section 5.1: "Although the Knuth-Morris-Pratt and Aho-Corasick algorithms have better worst-case running time than the Boyer-Moore and Commentz-Walter algorithms (respectively), the latter two algorithms are known to be extremely efficient in practice."		length of the input string. ...the running time of... CW-NORM depends (linearly...) upon the length of the shortest keyword in the keyword set." Additionally, in Section 5.1: "Although the Knuth-Morris-Pratt and Aho-Corasick algorithms have better worst-case running time than the Boyer-Moore and Commentz-Walter algorithms (respectively), the latter two algorithms are known to be extremely efficient in practice." <small><span class="autosigned">— Preceding [[Wikipedia:Signatures\|unsigned]] comment added by [[User:Doctor J\|Doctor J]] ([[User talk:Doctor J\|talk]] • [[Special:Contributions/Doctor J\|contribs]]) 22:27, 15 February 2012 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->

Doctor J: /* Asymptotic Runtime */ new section

2012-02-15T22:27:09Z

Asymptotic Runtime: new section

← Previous revision		Revision as of 22:27, 15 February 2012
Line 1:		Line 1:
	{{WikiProject Computer science}}		{{WikiProject Computer science}}

			== Asymptotic Runtime ==

			Watson's thesis (referenced), Algorithm 4.18 is given as a generalized precursor to CW, and remark 4.20 gives its runtime as O(S*P) for text length S and max pattern length P. The final derivation of CW (Section 4.4.5) does not give a runtime. Section 13.1 claims "All of the algorithms [including CW-NORM, normal Commentz-Walter]... have worst-case running time linear in the
			length of the input string. ...the running time of... CW-NORM depends (linearly...) upon the length of the shortest keyword in the keyword set." Additionally, in Section 5.1: "Although the Knuth-Morris-Pratt and Aho-Corasick algorithms have better worst-case running time than the Boyer-Moore and Commentz-Walter algorithms (respectively), the latter two algorithms are known to be extremely efficient in practice."

Ruud Koot: moved Talk:Commentz–Walter algorithm to Talk:Commentz-Walter algorithm: shouldn't be an en-dash

2011-12-05T01:14:02Z

moved Talk:Commentz–Walter algorithm to Talk:Commentz-Walter algorithm: shouldn't be an en-dash

← Previous revision	Revision as of 01:14, 5 December 2011
(No difference)

Ruud Koot: {{WikiProject Computer science}}

2011-12-05T01:11:50Z

← Previous revision		Revision as of 01:11, 5 December 2011
Line 1:		Line 1:
			{{WikiProject Computer science}}
	{{maths rating\|class=stub}}

Delusion23: corr

2011-10-12T12:50:41Z

corr

← Previous revision		Revision as of 12:50, 12 October 2011
Line 1:		Line 1:
	{{~~WikiProject~~ ~~Maths~~\|class=stub}}		{{maths rating\|class=stub}}

Delusion23: tag

2011-10-12T12:50:07Z

tag

New page