Two-way string-matching algorithm - Revision history

Cedar101: /* Critical factorization */ italics correction

2025-04-01T00:14:12Z

Critical factorization: italics correction

← Previous revision		Revision as of 00:14, 1 April 2025
Line 34:		Line 34:
	** {{mvar\|w}} is a prefix of {{mvar\|v}} or {{mvar\|v}} is a prefix of {{mvar\|w}};		** {{mvar\|w}} is a prefix of {{mvar\|v}} or {{mvar\|v}} is a prefix of {{mvar\|w}};
	*: In other words, {{mvar\|w}} occurs on both sides of the cut with a possible overflow on either side. Examples include <code>"an"</code> for <code>("ban","ana")</code> and <code>"voca"</code> for <code>("a","vocado")</code>. Each factorization trivially has at least one repetition: the string {{mvar\|vu}}.<ref name=igm-mlv/>		*: In other words, {{mvar\|w}} occurs on both sides of the cut with a possible overflow on either side. Examples include <code>"an"</code> for <code>("ban","ana")</code> and <code>"voca"</code> for <code>("a","vocado")</code>. Each factorization trivially has at least one repetition: the string {{mvar\|vu}}.<ref name=igm-mlv/>
	* A '''local period''' is the length of a repetition in {{tmath\|(u,v)}}. The smallest local period in {{tmath\|(u,v)}} is denoted as {{tmath\|r(u,v)}}. Because the trivial repetition {{~~math~~\|''vu''}} is guaranteed to exist and has the same length as {{mvar\|x}}, we see that {{tmath\|1 \le r(u,v) \le \mathrm{len}(x)}}.		* A '''local period''' is the length of a repetition in {{tmath\|(u,v)}}. The smallest local period in {{tmath\|(u,v)}} is denoted as {{tmath\|r(u,v)}}. Because the trivial repetition {{mvar\|vu}} is guaranteed to exist and has the same length as {{mvar\|x}}, we see that {{tmath\|1 \le r(u,v) \le \mathrm{len}(x)}}.
	* A '''critical factorization''' is a factorization {{tmath\|(u,v)}} of {{mvar\|x}} such that {{~~math~~\|~~1=''~~r(u,v)'' = ''p(x)''}}. The existence of a critical factorization is provably guaranteed.<ref name=CP91/> For a needle of length {{mvar\|m}} in an ordered alphabet, it can be computed in {{math\|2''m''}} comparisons, by computing the lexicographically larger of two ordered maximal suffixes, defined for order ≤ and ≥.<ref name=str-two-way/>		* A '''critical factorization''' is a factorization {{tmath\|(u,v)}} of {{mvar\|x}} such that {{tmath\|r(u,v) {{=}} p(x)}}. The existence of a critical factorization is provably guaranteed.<ref name=CP91/> For a needle of length {{mvar\|m}} in an ordered alphabet, it can be computed in {{math\|2''m''}} comparisons, by computing the lexicographically larger of two ordered maximal suffixes, defined for order ≤ and ≥.<ref name=str-two-way/>

	== The algorithm ==		== The algorithm ==

Cedar101: /* Critical factorization */ italics correction

2025-04-01T00:13:29Z

Critical factorization: italics correction

← Previous revision		Revision as of 00:13, 1 April 2025
Line 28:		Line 28:
	== Critical factorization ==		== Critical factorization ==
	Before we define critical factorization, we should define:<ref name=CP91/>		Before we define critical factorization, we should define:<ref name=CP91/>
	* A '''factorization''' is a partition {{~~math~~\|''(u,v)''}} of a string {{~~math~~\|''x''}}. For example, <code>("Wiki","pedia")</code> is a factorization of <code>"Wikipedia"</code>.		* A '''factorization''' is a partition {{tmath\|(u,v)}} of a string {{mvar\|x}}. For example, <code>("Wiki","pedia")</code> is a factorization of <code>"Wikipedia"</code>.
	* A '''period''' of a string {{~~math~~\|''x''}} is an integer {{~~math~~\|''p''}} such that all characters {{~~math~~\|''p''}}-distance apart are equal. More precisely, {{math\|1=''x''[''i''] = ''x''[''i'' + ''p'']}} holds for any integer {{math\|0 < ''i'' ≤ ''len(x)'' − ''p''}}. This definition is allowed to be vacuously true, so that any word of length {{~~math~~\|''n''}} has a period of {{~~math~~\|''n''}}. To illustrate, the 8-letter word <code>"educated"</code> has period 6 in addition to the trivial periods of 8 and above. The minimum period of {{~~math~~\|''x''}} is denoted as {{~~math~~\|''p(x)''}}.		* A '''period''' of a string {{mvar\|x}} is an integer {{mvar\|p}} such that all characters {{mvar\|p}}-distance apart are equal. More precisely, {{math\|1=''x''[''i''] = ''x''[''i'' + ''p'']}} holds for any integer {{math\|0 < ''i'' ≤ len(''x'') − ''p''}}. This definition is allowed to be vacuously true, so that any word of length {{mvar\|n}} has a period of {{mvar\|n}}. To illustrate, the 8-letter word <code>"educated"</code> has period 6 in addition to the trivial periods of 8 and above. The minimum period of {{mvar\|x}} is denoted as {{tmath\|p(x)}}.
	* A '''repetition''' {{~~math~~\|''w''}} in {{~~math~~\|''(u,v)''}} is a non-empty string such that:		* A '''repetition''' {{mvar\|w}} in {{tmath\|(u,v)}} is a non-empty string such that:
	** {{~~math~~\|''w''}} is a suffix of {{~~math~~\|''u''}} or {{~~math~~\|''u''}} is a suffix of {{~~math~~\|''w''}};		** {{mvar\|w}} is a suffix of {{mvar\|u}} or {{mvar\|u}} is a suffix of {{mvar\|w}};
	** {{~~math~~\|''w''}} is a prefix of {{~~math~~\|''v''}} or {{~~math~~\|''v''}} is a prefix of {{~~math~~\|''w''}};		** {{mvar\|w}} is a prefix of {{mvar\|v}} or {{mvar\|v}} is a prefix of {{mvar\|w}};
	*: In other words, {{~~math~~\|''w''}} occurs on both sides of the cut with a possible overflow on either side. Examples include <code>"an"</code> for <code>("ban","ana")</code> and <code>"voca"</code> for <code>("a","vocado")</code>. Each factorization trivially has at least one repetition: the string {{~~math~~\|''vu''}}.<ref name=igm-mlv/>		*: In other words, {{mvar\|w}} occurs on both sides of the cut with a possible overflow on either side. Examples include <code>"an"</code> for <code>("ban","ana")</code> and <code>"voca"</code> for <code>("a","vocado")</code>. Each factorization trivially has at least one repetition: the string {{mvar\|vu}}.<ref name=igm-mlv/>
	* A '''local period''' is the length of a repetition in {{~~math~~\|''(u,v)''}}. The smallest local period in {{~~math~~\|''(u,v)''}} is denoted as {{~~math~~\|''r(u,v)''}}. Because the trivial repetition {{math\|''vu''}} is guaranteed to exist and has the same length as {{~~math~~\|''x''}}, we see that {{~~math~~\|1 ≤ ''r(u,v)'' ≤ ''len(x)''}}.		* A '''local period''' is the length of a repetition in {{tmath\|(u,v)}}. The smallest local period in {{tmath\|(u,v)}} is denoted as {{tmath\|r(u,v)}}. Because the trivial repetition {{math\|''vu''}} is guaranteed to exist and has the same length as {{mvar\|x}}, we see that {{tmath\|1 \le r(u,v) \le \mathrm{len}(x)}}.
	* A '''critical factorization''' is a factorization {{~~math~~\|''(u,v)''}} of {{~~math~~\|''x''}} such that {{math\|1=''r(u,v)'' = ''p(x)''}}. The existence of a critical factorization is provably guaranteed.<ref name=CP91/> For a needle of length {{~~math~~\|''m''}} in an ordered alphabet, it can be computed in {{math\|2''m''}} comparisons, by computing the lexicographically larger of two ordered maximal suffixes, defined for order ≤ and ≥.<ref name=str-two-way/>		* A '''critical factorization''' is a factorization {{tmath\|(u,v)}} of {{mvar\|x}} such that {{math\|1=''r(u,v)'' = ''p(x)''}}. The existence of a critical factorization is provably guaranteed.<ref name=CP91/> For a needle of length {{mvar\|m}} in an ordered alphabet, it can be computed in {{math\|2''m''}} comparisons, by computing the lexicographically larger of two ordered maximal suffixes, defined for order ≤ and ≥.<ref name=str-two-way/>

	== The algorithm ==		== The algorithm ==

Mathlate: Fix citation for Critical factorization theorem

2025-01-28T18:10:26Z

Fix citation for Critical factorization theorem

← Previous revision		Revision as of 18:10, 28 January 2025
Line 35:		Line 35:
	*: In other words, {{math\|''w''}} occurs on both sides of the cut with a possible overflow on either side. Examples include <code>"an"</code> for <code>("ban","ana")</code> and <code>"voca"</code> for <code>("a","vocado")</code>. Each factorization trivially has at least one repetition: the string {{math\|''vu''}}.<ref name=igm-mlv/>		*: In other words, {{math\|''w''}} occurs on both sides of the cut with a possible overflow on either side. Examples include <code>"an"</code> for <code>("ban","ana")</code> and <code>"voca"</code> for <code>("a","vocado")</code>. Each factorization trivially has at least one repetition: the string {{math\|''vu''}}.<ref name=igm-mlv/>
	* A '''local period''' is the length of a repetition in {{math\|''(u,v)''}}. The smallest local period in {{math\|''(u,v)''}} is denoted as {{math\|''r(u,v)''}}. Because the trivial repetition {{math\|''vu''}} is guaranteed to exist and has the same length as {{math\|''x''}}, we see that {{math\|1 ≤ ''r(u,v)'' ≤ ''len(x)''}}.		* A '''local period''' is the length of a repetition in {{math\|''(u,v)''}}. The smallest local period in {{math\|''(u,v)''}} is denoted as {{math\|''r(u,v)''}}. Because the trivial repetition {{math\|''vu''}} is guaranteed to exist and has the same length as {{math\|''x''}}, we see that {{math\|1 ≤ ''r(u,v)'' ≤ ''len(x)''}}.
	* A '''critical factorization''' is a factorization {{math\|''(u,v)''}} of {{math\|''x''}} such that {{math\|1=''r(u,v)'' = ''p(x)''}}. The existence of a critical factorization is provably guaranteed.<ref name=~~str-two-way~~/> For a needle of length {{math\|''m''}} in an ordered alphabet, it can be computed in {{math\|2''m''}} comparisons, by computing the lexicographically larger of two ordered maximal suffixes, defined for order ≤ and ≥.<ref name=str-two-way/>		* A '''critical factorization''' is a factorization {{math\|''(u,v)''}} of {{math\|''x''}} such that {{math\|1=''r(u,v)'' = ''p(x)''}}. The existence of a critical factorization is provably guaranteed.<ref name=CP91/> For a needle of length {{math\|''m''}} in an ordered alphabet, it can be computed in {{math\|2''m''}} comparisons, by computing the lexicographically larger of two ordered maximal suffixes, defined for order ≤ and ≥.<ref name=str-two-way/>

	== The algorithm ==		== The algorithm ==

Mathlate: Updated the definitions to include examples, clearer wording, and more consistent style

2025-01-28T18:04:37Z

Updated the definitions to include examples, clearer wording, and more consistent style

← Previous revision		Revision as of 18:04, 28 January 2025
Line 28:		Line 28:
	== Critical factorization ==		== Critical factorization ==
	Before we define critical factorization, we should define:<ref name=CP91/>		Before we define critical factorization, we should define:<ref name=CP91/>
	* '''~~Factorization:~~''' ~~a string~~ is ~~considered factorized when it is split into two parts. Suppose~~ a ~~string~~ {{math\|''x''}} is ~~split~~ ~~into two parts~~ {{math\|''~~(u, v)~~''}}, ~~then {{math\|''~~(u, v)~~''}}~~ is ~~called~~ a factorization of ~~{{math\|''x''}}~~.		* A '''factorization''' is a partition {{math\|''(u,v)''}} of a string {{math\|''x''}}. For example, <code>("Wiki","pedia")</code> is a factorization of <code>"Wikipedia"</code>.
	* '''~~Period~~''': a ~~period~~ {{math\|''p''}} ~~for~~ a ~~string~~ {{math\|''x''}} ~~is defined as a value~~ such that ~~for~~ ~~any integer~~ {{math\|~~0 <~~ ''i'' ~~≤~~ ~~''len(x)''~~ − ~~''p''}}~~, {{math\|1=''x''[''i''] = ''x''[''i'' + ''p'']}}. In ~~other~~ ~~words,~~ "{{math\|''p''}} is a ~~period~~ ~~of {{math\|~~''x''}} if ~~two~~ ~~letters~~ of {{math\|''x''}} at ~~distance~~ {{math\|''p''}} ~~always~~ ~~coincide~~". The minimum period of {{math\|''x''}} is ~~a positive integer~~ denoted as {{math\|''p(x)''}}.		* A '''period''' of a string {{math\|''x''}} is an integer {{math\|''p''}} such that all characters {{math\|''p''}}-distance apart are equal. More precisely, {{math\|1=''x''[''i''] = ''x''[''i'' + ''p'']}} holds for any integer {{math\|0 < ''i'' ≤ ''len(x)'' − ''p''}}. This definition is allowed to be vacuously true, so that any word of length {{math\|''n''}} has a period of {{math\|''n''}}. To illustrate, the 8-letter word <code>"educated"</code> has period 6 in addition to the trivial periods of 8 and above. The minimum period of {{math\|''x''}} is denoted as {{math\|''p(x)''}}.
	* A '''repetition''' {{math\|''w''}} in {{math\|''(u, v)''}} is a non-empty string such that:		* A '''repetition''' {{math\|''w''}} in {{math\|''(u,v)''}} is a non-empty string such that:
	** {{math\|''w''}} is a suffix of {{math\|''u''}} or {{math\|''u''}} is a suffix of {{math\|''w''}};		** {{math\|''w''}} is a suffix of {{math\|''u''}} or {{math\|''u''}} is a suffix of {{math\|''w''}};
	** {{math\|''w''}} is a prefix of {{math\|''v''}} or {{math\|''v''}} is a prefix of {{math\|''w''}};		** {{math\|''w''}} is a prefix of {{math\|''v''}} or {{math\|''v''}} is a prefix of {{math\|''w''}};
	*: In other words, {{math\|''w''}} occurs on both sides of the cut with a possible overflow on either side. Each factorization trivially has at least one repetition, the string {{math\|''vu''}}.<ref name=igm-mlv/>		*: In other words, {{math\|''w''}} occurs on both sides of the cut with a possible overflow on either side. Examples include <code>"an"</code> for <code>("ban","ana")</code> and <code>"voca"</code> for <code>("a","vocado")</code>. Each factorization trivially has at least one repetition: the string {{math\|''vu''}}.<ref name=igm-mlv/>
	* A '''local period''' is the length of a repetition in {{math\|''(u, v)''}}. The smallest local period in {{math\|''(u, v)''}} is denoted as {{math\|''r(u, v)''}}. ~~For~~ ~~any~~ ~~factorization~~ {{math\|''~~(u, v)~~''}} of {{math\|''x''}}, {{math\|0 ~~<~~ ''r(u, v)'' ≤ ''len(x)''}}.		* A '''local period''' is the length of a repetition in {{math\|''(u,v)''}}. The smallest local period in {{math\|''(u,v)''}} is denoted as {{math\|''r(u,v)''}}. Because the trivial repetition {{math\|''vu''}} is guaranteed to exist and has the same length as {{math\|''x''}}, we see that {{math\|1 ≤ ''r(u,v)'' ≤ ''len(x)''}}.
	* A '''critical factorization''' is a factorization {{math\|''(u, v)''}} of {{math\|''x''}} such that {{math\|1=''r(u, v)'' = ''p(x)''}}. For a needle of length {{math\|''m''}} in an ordered alphabet, it can be computed in {{math\|2''m''}} comparisons, by computing the lexicographically larger of two ordered maximal suffixes, defined for order ≤ and ≥.<ref name=str-two-way/>		* A '''critical factorization''' is a factorization {{math\|''(u,v)''}} of {{math\|''x''}} such that {{math\|1=''r(u,v)'' = ''p(x)''}}. The existence of a critical factorization is provably guaranteed.<ref name=str-two-way/> For a needle of length {{math\|''m''}} in an ordered alphabet, it can be computed in {{math\|2''m''}} comparisons, by computing the lexicographically larger of two ordered maximal suffixes, defined for order ≤ and ≥.<ref name=str-two-way/>

	== The algorithm ==		== The algorithm ==

Gelingvistoj: /* Critical factorization */ The empty string is not a repetition.

2024-10-18T15:25:27Z

Critical factorization: The empty string is not a repetition.

← Previous revision		Revision as of 15:25, 18 October 2024
Line 30:		Line 30:
	* '''Factorization:''' a string is considered factorized when it is split into two parts. Suppose a string {{math\|''x''}} is split into two parts {{math\|''(u, v)''}}, then {{math\|''(u, v)''}} is called a factorization of {{math\|''x''}}.		* '''Factorization:''' a string is considered factorized when it is split into two parts. Suppose a string {{math\|''x''}} is split into two parts {{math\|''(u, v)''}}, then {{math\|''(u, v)''}} is called a factorization of {{math\|''x''}}.
	* '''Period''': a period {{math\|''p''}} for a string {{math\|''x''}} is defined as a value such that for any integer {{math\|0 < ''i'' ≤ ''len(x)'' − ''p''}}, {{math\|1=''x''[''i''] = ''x''[''i'' + ''p'']}}. In other words, "{{math\|''p''}} is a period of {{math\|''x''}} if two letters of {{math\|''x''}} at distance {{math\|''p''}} always coincide". The minimum period of {{math\|''x''}} is a positive integer denoted as {{math\|''p(x)''}}.		* '''Period''': a period {{math\|''p''}} for a string {{math\|''x''}} is defined as a value such that for any integer {{math\|0 < ''i'' ≤ ''len(x)'' − ''p''}}, {{math\|1=''x''[''i''] = ''x''[''i'' + ''p'']}}. In other words, "{{math\|''p''}} is a period of {{math\|''x''}} if two letters of {{math\|''x''}} at distance {{math\|''p''}} always coincide". The minimum period of {{math\|''x''}} is a positive integer denoted as {{math\|''p(x)''}}.
	* A '''repetition''' {{math\|''w''}} in {{math\|''(u, v)''}} is a string such that:		* A '''repetition''' {{math\|''w''}} in {{math\|''(u, v)''}} is a non-empty string such that:
	** {{math\|''w''}} is a suffix of {{math\|''u''}} or {{math\|''u''}} is a suffix of {{math\|''w''}};		** {{math\|''w''}} is a suffix of {{math\|''u''}} or {{math\|''u''}} is a suffix of {{math\|''w''}};
	** {{math\|''w''}} is a prefix of {{math\|''v''}} or {{math\|''v''}} is a prefix of {{math\|''w''}};		** {{math\|''w''}} is a prefix of {{math\|''v''}} or {{math\|''v''}} is a prefix of {{math\|''w''}};

Fschwarzentruber: /* Critical factorization */

2024-10-07T13:25:29Z

Critical factorization

← Previous revision		Revision as of 13:25, 7 October 2024
Line 34:		Line 34:
	** {{math\|''w''}} is a prefix of {{math\|''v''}} or {{math\|''v''}} is a prefix of {{math\|''w''}};		** {{math\|''w''}} is a prefix of {{math\|''v''}} or {{math\|''v''}} is a prefix of {{math\|''w''}};
	*: In other words, {{math\|''w''}} occurs on both sides of the cut with a possible overflow on either side. Each factorization trivially has at least one repetition, the string {{math\|''vu''}}.<ref name=igm-mlv/>		*: In other words, {{math\|''w''}} occurs on both sides of the cut with a possible overflow on either side. Each factorization trivially has at least one repetition, the string {{math\|''vu''}}.<ref name=igm-mlv/>
	* A '''local period''' is the length of a repetition in {{math\|''(u, v)''}}. The smallest local period in {{math\|''(u, v)''}} is denoted as {{math\|''r(u, v)''}}. For any factorization, {{math\|0 < ''r(u, v)'' ≤ ''len(x)''}}.		* A '''local period''' is the length of a repetition in {{math\|''(u, v)''}}. The smallest local period in {{math\|''(u, v)''}} is denoted as {{math\|''r(u, v)''}}. For any factorization {{math\|''(u, v)''}} of {{math\|''x''}}, {{math\|0 < ''r(u, v)'' ≤ ''len(x)''}}.
	* A '''critical factorization''' is a factorization {{math\|''(u, v)''}} of {{math\|''x''}} such that {{math\|1=''r(u, v)'' = ''p(x)''}}. For a needle of length {{math\|''m''}} in an ordered alphabet, it can be computed in {{math\|2''m''}} comparisons, by computing the lexicographically larger of two ordered maximal suffixes, defined for order ≤ and ≥.<ref name=str-two-way/>		* A '''critical factorization''' is a factorization {{math\|''(u, v)''}} of {{math\|''x''}} such that {{math\|1=''r(u, v)'' = ''p(x)''}}. For a needle of length {{math\|''m''}} in an ordered alphabet, it can be computed in {{math\|2''m''}} comparisons, by computing the lexicographically larger of two ordered maximal suffixes, defined for order ≤ and ≥.<ref name=str-two-way/>

Belbury: Adding short description: "String-searching algorithm"

2024-08-14T12:30:23Z

Adding short description: "String-searching algorithm"

← Previous revision		Revision as of 12:30, 14 August 2024
Line 1:		Line 1:
			{{Short description\|String-searching algorithm}}
	{{Infobox algorithm		{{Infobox algorithm
	\|name = <!-- Defaults to article name -->		\|name = <!-- Defaults to article name -->

Asd142513: /* Critical factorization */

2024-07-15T08:04:56Z

Critical factorization

← Previous revision		Revision as of 08:04, 15 July 2024
Line 28:		Line 28:
	Before we define critical factorization, we should define:<ref name=CP91/>		Before we define critical factorization, we should define:<ref name=CP91/>
	* '''Factorization:''' a string is considered factorized when it is split into two parts. Suppose a string {{math\|''x''}} is split into two parts {{math\|''(u, v)''}}, then {{math\|''(u, v)''}} is called a factorization of {{math\|''x''}}.		* '''Factorization:''' a string is considered factorized when it is split into two parts. Suppose a string {{math\|''x''}} is split into two parts {{math\|''(u, v)''}}, then {{math\|''(u, v)''}} is called a factorization of {{math\|''x''}}.
	* '''Period''': a period {{math\|''p''}} for a string {{math\|''x''}} is defined as a value such that for any integer {{math\|0 ≤ ''i'' < ''len(x)'' − ''p''}}, {{math\|1=''x''[''i''] = ''x''[''i'' + ''p'']}}. In other words, "{{math\|''p''}} is a period of {{math\|''x''}} if two letters of {{math\|''x''}} at distance {{math\|''p''}} always coincide". The minimum period of {{math\|''x''}} is a positive integer denoted as {{math\|''p(x)''}}.		* '''Period''': a period {{math\|''p''}} for a string {{math\|''x''}} is defined as a value such that for any integer {{math\|0 < ''i'' ≤ ''len(x)'' − ''p''}}, {{math\|1=''x''[''i''] = ''x''[''i'' + ''p'']}}. In other words, "{{math\|''p''}} is a period of {{math\|''x''}} if two letters of {{math\|''x''}} at distance {{math\|''p''}} always coincide". The minimum period of {{math\|''x''}} is a positive integer denoted as {{math\|''p(x)''}}.
	* A '''repetition''' {{math\|''w''}} in {{math\|''(u, v)''}} is a string such that:		* A '''repetition''' {{math\|''w''}} in {{math\|''(u, v)''}} is a string such that:
	** {{math\|''w''}} is a suffix of {{math\|''u''}} or {{math\|''u''}} is a suffix of {{math\|''w''}};		** {{math\|''w''}} is a suffix of {{math\|''u''}} or {{math\|''u''}} is a suffix of {{math\|''w''}};
	** {{math\|''w''}} is a prefix of {{math\|''v''}} or {{math\|''v''}} is a prefix of {{math\|''w''}};		** {{math\|''w''}} is a prefix of {{math\|''v''}} or {{math\|''v''}} is a prefix of {{math\|''w''}};
	*: In other words, {{math\|''w''}} occurs on both sides of the cut with a possible overflow on either side. Each factorization trivially has at least one repetition, the string {{math\|''vu''}}.<ref name=igm-mlv/>		*: In other words, {{math\|''w''}} occurs on both sides of the cut with a possible overflow on either side. Each factorization trivially has at least one repetition, the string {{math\|''vu''}}.<ref name=igm-mlv/>
	* A '''local period''' is the length of a repetition in {{math\|''(u, v)''}}. The smallest local period in {{math\|''(u, v)''}} is denoted as {{math\|''r(u, v)''}}. For any factorization, {{math\|0 < ''r(u, v)'' ≤ ~~{{!}}~~''x''~~{{!}}~~}}.		* A '''local period''' is the length of a repetition in {{math\|''(u, v)''}}. The smallest local period in {{math\|''(u, v)''}} is denoted as {{math\|''r(u, v)''}}. For any factorization, {{math\|0 < ''r(u, v)'' ≤ ''len(x)''}}.
	* A '''critical factorization''' is a factorization {{math\|''(u, v)''}} of {{math\|''x''}} such that {{math\|1=''r(u, v)'' = ''p(x)''}}. For a needle of length {{math\|''m''}} in an ordered alphabet, it can be computed in {{math\|2''m''}} comparisons, by computing the lexicographically larger of two ordered maximal suffixes, defined for order ≤ and ≥.<ref name=str-two-way/>		* A '''critical factorization''' is a factorization {{math\|''(u, v)''}} of {{math\|''x''}} such that {{math\|1=''r(u, v)'' = ''p(x)''}}. For a needle of length {{math\|''m''}} in an ordered alphabet, it can be computed in {{math\|2''m''}} comparisons, by computing the lexicographically larger of two ordered maximal suffixes, defined for order ≤ and ≥.<ref name=str-two-way/>

Asd142513 at 07:47, 15 July 2024

2024-07-15T07:47:56Z

← Previous revision		Revision as of 07:47, 15 July 2024
Line 30:		Line 30:
	* '''Period''': a period {{math\|''p''}} for a string {{math\|''x''}} is defined as a value such that for any integer {{math\|0 ≤ ''i'' < ''len(x)'' − ''p''}}, {{math\|1=''x''[''i''] = ''x''[''i'' + ''p'']}}. In other words, "{{math\|''p''}} is a period of {{math\|''x''}} if two letters of {{math\|''x''}} at distance {{math\|''p''}} always coincide". The minimum period of {{math\|''x''}} is a positive integer denoted as {{math\|''p(x)''}}.		* '''Period''': a period {{math\|''p''}} for a string {{math\|''x''}} is defined as a value such that for any integer {{math\|0 ≤ ''i'' < ''len(x)'' − ''p''}}, {{math\|1=''x''[''i''] = ''x''[''i'' + ''p'']}}. In other words, "{{math\|''p''}} is a period of {{math\|''x''}} if two letters of {{math\|''x''}} at distance {{math\|''p''}} always coincide". The minimum period of {{math\|''x''}} is a positive integer denoted as {{math\|''p(x)''}}.
	* A '''repetition''' {{math\|''w''}} in {{math\|''(u, v)''}} is a string such that:		* A '''repetition''' {{math\|''w''}} in {{math\|''(u, v)''}} is a string such that:
	** {{math\|''w''}} is a suffix of {{math\|''u''}} or ~~the~~ ~~other~~ ~~way~~ ~~around~~;		** {{math\|''w''}} is a suffix of {{math\|''u''}} or {{math\|''u''}} is a suffix of {{math\|''w''}};
	** {{math\|''w''}} is a prefix of {{math\|''v''}} or ~~the~~ ~~other~~ ~~way~~ ~~around~~;		** {{math\|''w''}} is a prefix of {{math\|''v''}} or {{math\|''v''}} is a prefix of {{math\|''w''}};
	*: In other words, {{math\|''w''}} occurs on both sides of the cut with a possible overflow on either side. Each factorization trivially has at least one repetition, the string {{math\|''vu''}}.<ref name=igm-mlv/>		*: In other words, {{math\|''w''}} occurs on both sides of the cut with a possible overflow on either side. Each factorization trivially has at least one repetition, the string {{math\|''vu''}}.<ref name=igm-mlv/>
	* A '''local period''' is the length of a repetition in {{math\|''(u, v)''}}. The smallest local period in {{math\|''(u, v)''}} is denoted as {{math\|''r(u, v)''}}. For any factorization, {{math\|0 < ''r(u, v)'' ≤ {{!}}''x''{{!}}}}.		* A '''local period''' is the length of a repetition in {{math\|''(u, v)''}}. The smallest local period in {{math\|''(u, v)''}} is denoted as {{math\|''r(u, v)''}}. For any factorization, {{math\|0 < ''r(u, v)'' ≤ {{!}}''x''{{!}}}}.

Asd142513: /* Critical factorization */

2024-07-15T06:02:46Z

Critical factorization

← Previous revision		Revision as of 06:02, 15 July 2024
Line 28:		Line 28:
	Before we define critical factorization, we should define:<ref name=CP91/>		Before we define critical factorization, we should define:<ref name=CP91/>
	* '''Factorization:''' a string is considered factorized when it is split into two parts. Suppose a string {{math\|''x''}} is split into two parts {{math\|''(u, v)''}}, then {{math\|''(u, v)''}} is called a factorization of {{math\|''x''}}.		* '''Factorization:''' a string is considered factorized when it is split into two parts. Suppose a string {{math\|''x''}} is split into two parts {{math\|''(u, v)''}}, then {{math\|''(u, v)''}} is called a factorization of {{math\|''x''}}.
	* '''Period''': a period {{math\|''p''}} for a string {{math\|''x''}} is defined as a value such that for any integer {{math\|0 < ''i'' ≤ ~~{{!}}~~''x''~~{{!}}~~ − ''p''}}, {{math\|1=''x''[''i''] = ''x''[''i'' + ''p'']}}. In other words, "{{math\|''p''}} is a period of {{math\|''x''}} if two letters of {{math\|''x''}} at distance {{math\|''p''}} always coincide". The minimum period of {{math\|''x''}} is a positive integer denoted as {{math\|''p(x)''}}.		* '''Period''': a period {{math\|''p''}} for a string {{math\|''x''}} is defined as a value such that for any integer {{math\|0 ≤ ''i'' < ''len(x)'' − ''p''}}, {{math\|1=''x''[''i''] = ''x''[''i'' + ''p'']}}. In other words, "{{math\|''p''}} is a period of {{math\|''x''}} if two letters of {{math\|''x''}} at distance {{math\|''p''}} always coincide". The minimum period of {{math\|''x''}} is a positive integer denoted as {{math\|''p(x)''}}.
	* A '''repetition''' {{math\|''w''}} in {{math\|''(u, v)''}} is a string such that:		* A '''repetition''' {{math\|''w''}} in {{math\|''(u, v)''}} is a string such that:
	** {{math\|''w''}} is a suffix of {{math\|''u''}} or the other way around;		** {{math\|''w''}} is a suffix of {{math\|''u''}} or the other way around;

← Previous revision		Revision as of 00:14, 1 April 2025
Line 34:		Line 34:
	** {{mvar\|w}} is a prefix of {{mvar\|v}} or {{mvar\|v}} is a prefix of {{mvar\|w}};		** {{mvar\|w}} is a prefix of {{mvar\|v}} or {{mvar\|v}} is a prefix of {{mvar\|w}};
	*: In other words, {{mvar\|w}} occurs on both sides of the cut with a possible overflow on either side. Examples include <code>"an"</code> for <code>("ban","ana")</code> and <code>"voca"</code> for <code>("a","vocado")</code>. Each factorization trivially has at least one repetition: the string {{mvar\|vu}}.<ref name=igm-mlv/>		*: In other words, {{mvar\|w}} occurs on both sides of the cut with a possible overflow on either side. Examples include <code>"an"</code> for <code>("ban","ana")</code> and <code>"voca"</code> for <code>("a","vocado")</code>. Each factorization trivially has at least one repetition: the string {{mvar\|vu}}.<ref name=igm-mlv/>
	* A '''local period''' is the length of a repetition in {{tmath\|(u,v)}}. The smallest local period in {{tmath\|(u,v)}} is denoted as {{tmath\|r(u,v)}}. Because the trivial repetition {{~~math~~\|''vu''}} is guaranteed to exist and has the same length as {{mvar\|x}}, we see that {{tmath\|1 \le r(u,v) \le \mathrm{len}(x)}}.		* A '''local period''' is the length of a repetition in {{tmath\|(u,v)}}. The smallest local period in {{tmath\|(u,v)}} is denoted as {{tmath\|r(u,v)}}. Because the trivial repetition {{mvar\|vu}} is guaranteed to exist and has the same length as {{mvar\|x}}, we see that {{tmath\|1 \le r(u,v) \le \mathrm{len}(x)}}.
	* A '''critical factorization''' is a factorization {{tmath\|(u,v)}} of {{mvar\|x}} such that {{~~math~~\|~~1=''~~r(u,v)'' = ''p(x)''}}. The existence of a critical factorization is provably guaranteed.<ref name=CP91/> For a needle of length {{mvar\|m}} in an ordered alphabet, it can be computed in {{math\|2''m''}} comparisons, by computing the lexicographically larger of two ordered maximal suffixes, defined for order ≤ and ≥.<ref name=str-two-way/>		* A '''critical factorization''' is a factorization {{tmath\|(u,v)}} of {{mvar\|x}} such that {{tmath\|r(u,v) {{=}} p(x)}}. The existence of a critical factorization is provably guaranteed.<ref name=CP91/> For a needle of length {{mvar\|m}} in an ordered alphabet, it can be computed in {{math\|2''m''}} comparisons, by computing the lexicographically larger of two ordered maximal suffixes, defined for order ≤ and ≥.<ref name=str-two-way/>

	== The algorithm ==		== The algorithm ==

← Previous revision		Revision as of 00:13, 1 April 2025
Line 28:		Line 28:
	== Critical factorization ==		== Critical factorization ==
	Before we define critical factorization, we should define:<ref name=CP91/>		Before we define critical factorization, we should define:<ref name=CP91/>
	* A '''factorization''' is a partition {{~~math~~\|''(u,v)''}} of a string {{~~math~~\|''x''}}. For example, <code>("Wiki","pedia")</code> is a factorization of <code>"Wikipedia"</code>.		* A '''factorization''' is a partition {{tmath\|(u,v)}} of a string {{mvar\|x}}. For example, <code>("Wiki","pedia")</code> is a factorization of <code>"Wikipedia"</code>.
	* A '''period''' of a string {{~~math~~\|''x''}} is an integer {{~~math~~\|''p''}} such that all characters {{~~math~~\|''p''}}-distance apart are equal. More precisely, {{math\|1=''x''[''i''] = ''x''[''i'' + ''p'']}} holds for any integer {{math\|0 < ''i'' ≤ ''len(x)'' − ''p''}}. This definition is allowed to be vacuously true, so that any word of length {{~~math~~\|''n''}} has a period of {{~~math~~\|''n''}}. To illustrate, the 8-letter word <code>"educated"</code> has period 6 in addition to the trivial periods of 8 and above. The minimum period of {{~~math~~\|''x''}} is denoted as {{~~math~~\|''p(x)''}}.		* A '''period''' of a string {{mvar\|x}} is an integer {{mvar\|p}} such that all characters {{mvar\|p}}-distance apart are equal. More precisely, {{math\|1=''x''[''i''] = ''x''[''i'' + ''p'']}} holds for any integer {{math\|0 < ''i'' ≤ len(''x'') − ''p''}}. This definition is allowed to be vacuously true, so that any word of length {{mvar\|n}} has a period of {{mvar\|n}}. To illustrate, the 8-letter word <code>"educated"</code> has period 6 in addition to the trivial periods of 8 and above. The minimum period of {{mvar\|x}} is denoted as {{tmath\|p(x)}}.
	* A '''repetition''' {{~~math~~\|''w''}} in {{~~math~~\|''(u,v)''}} is a non-empty string such that:		* A '''repetition''' {{mvar\|w}} in {{tmath\|(u,v)}} is a non-empty string such that:
	** {{~~math~~\|''w''}} is a suffix of {{~~math~~\|''u''}} or {{~~math~~\|''u''}} is a suffix of {{~~math~~\|''w''}};		** {{mvar\|w}} is a suffix of {{mvar\|u}} or {{mvar\|u}} is a suffix of {{mvar\|w}};
	** {{~~math~~\|''w''}} is a prefix of {{~~math~~\|''v''}} or {{~~math~~\|''v''}} is a prefix of {{~~math~~\|''w''}};		** {{mvar\|w}} is a prefix of {{mvar\|v}} or {{mvar\|v}} is a prefix of {{mvar\|w}};
	*: In other words, {{~~math~~\|''w''}} occurs on both sides of the cut with a possible overflow on either side. Examples include <code>"an"</code> for <code>("ban","ana")</code> and <code>"voca"</code> for <code>("a","vocado")</code>. Each factorization trivially has at least one repetition: the string {{~~math~~\|''vu''}}.<ref name=igm-mlv/>		*: In other words, {{mvar\|w}} occurs on both sides of the cut with a possible overflow on either side. Examples include <code>"an"</code> for <code>("ban","ana")</code> and <code>"voca"</code> for <code>("a","vocado")</code>. Each factorization trivially has at least one repetition: the string {{mvar\|vu}}.<ref name=igm-mlv/>
	* A '''local period''' is the length of a repetition in {{~~math~~\|''(u,v)''}}. The smallest local period in {{~~math~~\|''(u,v)''}} is denoted as {{~~math~~\|''r(u,v)''}}. Because the trivial repetition {{math\|''vu''}} is guaranteed to exist and has the same length as {{~~math~~\|''x''}}, we see that {{~~math~~\|1 ≤ ''r(u,v)'' ≤ ''len(x)''}}.		* A '''local period''' is the length of a repetition in {{tmath\|(u,v)}}. The smallest local period in {{tmath\|(u,v)}} is denoted as {{tmath\|r(u,v)}}. Because the trivial repetition {{math\|''vu''}} is guaranteed to exist and has the same length as {{mvar\|x}}, we see that {{tmath\|1 \le r(u,v) \le \mathrm{len}(x)}}.
	* A '''critical factorization''' is a factorization {{~~math~~\|''(u,v)''}} of {{~~math~~\|''x''}} such that {{math\|1=''r(u,v)'' = ''p(x)''}}. The existence of a critical factorization is provably guaranteed.<ref name=CP91/> For a needle of length {{~~math~~\|''m''}} in an ordered alphabet, it can be computed in {{math\|2''m''}} comparisons, by computing the lexicographically larger of two ordered maximal suffixes, defined for order ≤ and ≥.<ref name=str-two-way/>		* A '''critical factorization''' is a factorization {{tmath\|(u,v)}} of {{mvar\|x}} such that {{math\|1=''r(u,v)'' = ''p(x)''}}. The existence of a critical factorization is provably guaranteed.<ref name=CP91/> For a needle of length {{mvar\|m}} in an ordered alphabet, it can be computed in {{math\|2''m''}} comparisons, by computing the lexicographically larger of two ordered maximal suffixes, defined for order ≤ and ≥.<ref name=str-two-way/>

	== The algorithm ==		== The algorithm ==

← Previous revision		Revision as of 18:04, 28 January 2025
Line 28:		Line 28:
	== Critical factorization ==		== Critical factorization ==
	Before we define critical factorization, we should define:<ref name=CP91/>		Before we define critical factorization, we should define:<ref name=CP91/>
	* '''~~Factorization:~~''' ~~a string~~ is ~~considered factorized when it is split into two parts. Suppose~~ a ~~string~~ {{math\|''x''}} is ~~split~~ ~~into two parts~~ {{math\|''~~(u, v)~~''}}, ~~then {{math\|''~~(u, v)~~''}}~~ is ~~called~~ a factorization of ~~{{math\|''x''}}~~.		* A '''factorization''' is a partition {{math\|''(u,v)''}} of a string {{math\|''x''}}. For example, <code>("Wiki","pedia")</code> is a factorization of <code>"Wikipedia"</code>.
	* '''~~Period~~''': a ~~period~~ {{math\|''p''}} ~~for~~ a ~~string~~ {{math\|''x''}} ~~is defined as a value~~ such that ~~for~~ ~~any integer~~ {{math\|~~0 <~~ ''i'' ~~≤~~ ~~''len(x)''~~ − ~~''p''}}~~, {{math\|1=''x''[''i''] = ''x''[''i'' + ''p'']}}. In ~~other~~ ~~words,~~ "{{math\|''p''}} is a ~~period~~ ~~of {{math\|~~''x''}} if ~~two~~ ~~letters~~ of {{math\|''x''}} at ~~distance~~ {{math\|''p''}} ~~always~~ ~~coincide~~". The minimum period of {{math\|''x''}} is ~~a positive integer~~ denoted as {{math\|''p(x)''}}.		* A '''period''' of a string {{math\|''x''}} is an integer {{math\|''p''}} such that all characters {{math\|''p''}}-distance apart are equal. More precisely, {{math\|1=''x''[''i''] = ''x''[''i'' + ''p'']}} holds for any integer {{math\|0 < ''i'' ≤ ''len(x)'' − ''p''}}. This definition is allowed to be vacuously true, so that any word of length {{math\|''n''}} has a period of {{math\|''n''}}. To illustrate, the 8-letter word <code>"educated"</code> has period 6 in addition to the trivial periods of 8 and above. The minimum period of {{math\|''x''}} is denoted as {{math\|''p(x)''}}.
	* A '''repetition''' {{math\|''w''}} in {{math\|''(u, v)''}} is a non-empty string such that:		* A '''repetition''' {{math\|''w''}} in {{math\|''(u,v)''}} is a non-empty string such that:
	** {{math\|''w''}} is a suffix of {{math\|''u''}} or {{math\|''u''}} is a suffix of {{math\|''w''}};		** {{math\|''w''}} is a suffix of {{math\|''u''}} or {{math\|''u''}} is a suffix of {{math\|''w''}};
	** {{math\|''w''}} is a prefix of {{math\|''v''}} or {{math\|''v''}} is a prefix of {{math\|''w''}};		** {{math\|''w''}} is a prefix of {{math\|''v''}} or {{math\|''v''}} is a prefix of {{math\|''w''}};
	*: In other words, {{math\|''w''}} occurs on both sides of the cut with a possible overflow on either side. Each factorization trivially has at least one repetition, the string {{math\|''vu''}}.<ref name=igm-mlv/>		*: In other words, {{math\|''w''}} occurs on both sides of the cut with a possible overflow on either side. Examples include <code>"an"</code> for <code>("ban","ana")</code> and <code>"voca"</code> for <code>("a","vocado")</code>. Each factorization trivially has at least one repetition: the string {{math\|''vu''}}.<ref name=igm-mlv/>
	* A '''local period''' is the length of a repetition in {{math\|''(u, v)''}}. The smallest local period in {{math\|''(u, v)''}} is denoted as {{math\|''r(u, v)''}}. ~~For~~ ~~any~~ ~~factorization~~ {{math\|''~~(u, v)~~''}} of {{math\|''x''}}, {{math\|0 ~~<~~ ''r(u, v)'' ≤ ''len(x)''}}.		* A '''local period''' is the length of a repetition in {{math\|''(u,v)''}}. The smallest local period in {{math\|''(u,v)''}} is denoted as {{math\|''r(u,v)''}}. Because the trivial repetition {{math\|''vu''}} is guaranteed to exist and has the same length as {{math\|''x''}}, we see that {{math\|1 ≤ ''r(u,v)'' ≤ ''len(x)''}}.
	* A '''critical factorization''' is a factorization {{math\|''(u, v)''}} of {{math\|''x''}} such that {{math\|1=''r(u, v)'' = ''p(x)''}}. For a needle of length {{math\|''m''}} in an ordered alphabet, it can be computed in {{math\|2''m''}} comparisons, by computing the lexicographically larger of two ordered maximal suffixes, defined for order ≤ and ≥.<ref name=str-two-way/>		* A '''critical factorization''' is a factorization {{math\|''(u,v)''}} of {{math\|''x''}} such that {{math\|1=''r(u,v)'' = ''p(x)''}}. The existence of a critical factorization is provably guaranteed.<ref name=str-two-way/> For a needle of length {{math\|''m''}} in an ordered alphabet, it can be computed in {{math\|2''m''}} comparisons, by computing the lexicographically larger of two ordered maximal suffixes, defined for order ≤ and ≥.<ref name=str-two-way/>

	== The algorithm ==		== The algorithm ==

← Previous revision		Revision as of 15:25, 18 October 2024
Line 30:		Line 30:
	* '''Factorization:''' a string is considered factorized when it is split into two parts. Suppose a string {{math\|''x''}} is split into two parts {{math\|''(u, v)''}}, then {{math\|''(u, v)''}} is called a factorization of {{math\|''x''}}.		* '''Factorization:''' a string is considered factorized when it is split into two parts. Suppose a string {{math\|''x''}} is split into two parts {{math\|''(u, v)''}}, then {{math\|''(u, v)''}} is called a factorization of {{math\|''x''}}.
	* '''Period''': a period {{math\|''p''}} for a string {{math\|''x''}} is defined as a value such that for any integer {{math\|0 < ''i'' ≤ ''len(x)'' − ''p''}}, {{math\|1=''x''[''i''] = ''x''[''i'' + ''p'']}}. In other words, "{{math\|''p''}} is a period of {{math\|''x''}} if two letters of {{math\|''x''}} at distance {{math\|''p''}} always coincide". The minimum period of {{math\|''x''}} is a positive integer denoted as {{math\|''p(x)''}}.		* '''Period''': a period {{math\|''p''}} for a string {{math\|''x''}} is defined as a value such that for any integer {{math\|0 < ''i'' ≤ ''len(x)'' − ''p''}}, {{math\|1=''x''[''i''] = ''x''[''i'' + ''p'']}}. In other words, "{{math\|''p''}} is a period of {{math\|''x''}} if two letters of {{math\|''x''}} at distance {{math\|''p''}} always coincide". The minimum period of {{math\|''x''}} is a positive integer denoted as {{math\|''p(x)''}}.
	* A '''repetition''' {{math\|''w''}} in {{math\|''(u, v)''}} is a string such that:		* A '''repetition''' {{math\|''w''}} in {{math\|''(u, v)''}} is a non-empty string such that:
	** {{math\|''w''}} is a suffix of {{math\|''u''}} or {{math\|''u''}} is a suffix of {{math\|''w''}};		** {{math\|''w''}} is a suffix of {{math\|''u''}} or {{math\|''u''}} is a suffix of {{math\|''w''}};
	** {{math\|''w''}} is a prefix of {{math\|''v''}} or {{math\|''v''}} is a prefix of {{math\|''w''}};		** {{math\|''w''}} is a prefix of {{math\|''v''}} or {{math\|''v''}} is a prefix of {{math\|''w''}};

← Previous revision		Revision as of 13:25, 7 October 2024
Line 34:		Line 34:
	** {{math\|''w''}} is a prefix of {{math\|''v''}} or {{math\|''v''}} is a prefix of {{math\|''w''}};		** {{math\|''w''}} is a prefix of {{math\|''v''}} or {{math\|''v''}} is a prefix of {{math\|''w''}};
	*: In other words, {{math\|''w''}} occurs on both sides of the cut with a possible overflow on either side. Each factorization trivially has at least one repetition, the string {{math\|''vu''}}.<ref name=igm-mlv/>		*: In other words, {{math\|''w''}} occurs on both sides of the cut with a possible overflow on either side. Each factorization trivially has at least one repetition, the string {{math\|''vu''}}.<ref name=igm-mlv/>
	* A '''local period''' is the length of a repetition in {{math\|''(u, v)''}}. The smallest local period in {{math\|''(u, v)''}} is denoted as {{math\|''r(u, v)''}}. For any factorization, {{math\|0 < ''r(u, v)'' ≤ ''len(x)''}}.		* A '''local period''' is the length of a repetition in {{math\|''(u, v)''}}. The smallest local period in {{math\|''(u, v)''}} is denoted as {{math\|''r(u, v)''}}. For any factorization {{math\|''(u, v)''}} of {{math\|''x''}}, {{math\|0 < ''r(u, v)'' ≤ ''len(x)''}}.
	* A '''critical factorization''' is a factorization {{math\|''(u, v)''}} of {{math\|''x''}} such that {{math\|1=''r(u, v)'' = ''p(x)''}}. For a needle of length {{math\|''m''}} in an ordered alphabet, it can be computed in {{math\|2''m''}} comparisons, by computing the lexicographically larger of two ordered maximal suffixes, defined for order ≤ and ≥.<ref name=str-two-way/>		* A '''critical factorization''' is a factorization {{math\|''(u, v)''}} of {{math\|''x''}} such that {{math\|1=''r(u, v)'' = ''p(x)''}}. For a needle of length {{math\|''m''}} in an ordered alphabet, it can be computed in {{math\|2''m''}} comparisons, by computing the lexicographically larger of two ordered maximal suffixes, defined for order ≤ and ≥.<ref name=str-two-way/>