Revision as of 21:13, 16 May 2023 edit 2804:7f2:2481:3321:b89b:255b:f48b:83a1 (talk) →Slow algorithm ← Previous edit		Revision as of 19:35, 19 August 2023 edit undo 182.69.181.26 (talk) →Runtime: It is given in the code for manachers algo that "while Center < length(S')" that is less than 2n+1 not less than equal. I changed 2n+1 to 2n to correct it. Tags: Reverted Visual edit Next edit →
Line 166: ===Runtime=== The algorithm runs in linear time. This can be seen by noting that <code>Center</code> strictly increases after each outer loop and the sum <code>Center + Radius</code> is non-decreasing. Moreover, the number of operations in the first inner loop is linear in the increase of the sum <code>Center + Radius</code> while the number of operations in the second inner loop is linear in the increase of <code>Center</code>. Since <code>Center ≤ 2n+1</code> and <code>Radius ≤ n</code>, the total number of operations in the first and second inner loops is <math>O(n)</math> and the total number of operations in the outer loop, other than those in the inner loops, is also <math>O(n)</math>. The overall running time is therefore <math>O(n)</math>. ==Notes==

Longest palindromic substring: Difference between revisions