python' string class strings are very important in python we introduced their use in with discussion of various operator syntaxes in section comprehensive summary of the named methods of the class is given in tables through of appendix we will not formally analyze the efficiency of each of those behaviors in this sectionbut we do wish to comment on some notable issues in generalwe let denote the length of string for operations that rely on second string as patternwe let denote the length of that pattern string the analysis for many behaviors is quite intuitive for examplemethods that produce new string ( capitalizecenterstriprequire time that is linear in the length of the string that is produced many of the behaviors that test boolean conditions of string ( islowertake (ntimeexamining all characters in the worst casebut short circuiting as soon as the answer becomes evident ( islower can immediately return false if the first character is uppercasedthe comparison operators ( ==<fall into this category as well pattern matching some of the most interesting behaviorsfrom an algorithmic point of vieware those that in some way depend upon finding string pattern within larger stringthis goal is at the heart of methods such as contains findindexcountreplaceand split string algorithms will be the topic of and this particular problem known as pattern matching will be the focus of section naive implementation runs in (mntime casebecause we consider the possible starting indices for the patternand we spend (mtime at each starting positionchecking if the pattern matches howeverin section we will develop an algorithm for finding pattern of length within longer string of length in (ntime composing strings finallywe wish to comment on several approaches for composing large strings as an academic exerciseassume that we have large string named documentand our goal is to produce new stringlettersthat contains only the alphabetic characters of the original string ( with spacesnumbersand punctuation removedit may be tempting to compose result through repeated concatenationas follows warningdo not do this letters for in documentif isalpha)letters + start with empty string concatenate alphabetic character