出版时间：2009-9 出版社：清华大学出版社 作者：斯基恩纳 页数：706
Most professional programmers that I've encountered are not well prepared to tackle algorithm design problems. This is a pity, because the techniques of algorithm design form one of the core practical technologies of computer science. Designing correct, efficient, and implementable algorithms for real-world problems requires access to two distinct bodies of knowledge:Techniques - Good algorithm designers understand several fundamental al-gorithm design techniques, including data structures, dynamic programming,depth-first search, backtracking, and heuristics. Perhaps the single most im-portant design technique is modeling, the art of abstracting a messy real-worldapplication into a clean problem suitable for algorithmic attack.Resources - Good algorithm designers stand on the shoulders of giants. Rather than laboring from scratch to produce a new algorithm for every task, they can figure out what is known about a particular problem. Rather than re-implementing popular algorithms from scratch, they seek existing imple- mentations to serve as a starting point. They are familiar with many classic algorithmic problems, which provide sufficient source material to model most any application.This book is intended as a manual on algorithm design, providing access tocombinatorial algorithm technology for both students and computer professionals.It is divided into two parts: Techniques and Resources, The former is a generalguide to techniques for the design and analysis of computer algorithms. The Re-sources section is intended for browsing and reference, and comprises the catalogof algorithmic resources, implementations, and an extensive bibliography.
I Practical Algorithm Design 1 Introduction to Algorithm Design 1.1 Robot Tour Optimization 1.2 Selecting the Right Jobs 1.3 Reasoning about Correctness 1.4 Modeling the Problem 1.5 About the War Stories 1.6 War Story: Psychic Modeling 1.7 Exercises 2 Algorithm Analysis 2.1 The RAM Model of Computation 2.2 The Big Oh Notation 2.3 Growth Rates and Dominance Relations 2.4 Working with the Big Oh 2.5 Reasoning About Efficiency 2.6 Logarithms and Their Applications 2.7 Properties of Logarithms 2.8 War Story: Mystery of the Pyramids 2.9 Advanced Analysis (*) 2.10 Exercises 3 Data Structures 3.1 Contiguous vs. Linked Data Structures. 3.2 Stacks and Queues 3.3 Dictionaries 3.4 Binary Search Trees 3.5 Priority Queues 3.6 War Story: Stripping Triangulations 3.7 Hashing and Strings 3.8 Specialized Data Structures 3.9 War Story: String 'em Up 3.10 Exercises 4 Sorting and Searching 4.1 Applications of Sorting 4.2 Pragmatics of Sorting 4.3 Heapsort: Fast Sorting via Data Structures 4.4 War Story: Give me a Ticket on an Airplane 4.5 Mergesort: Sorting by Divide-and-Conquer 4.6 Quicksort: Sorting by Randomization 4.7 Distribution Sort: Sorting via Bucketing 4.8 War Story: Skiena for the Defense 4.9 Binary Search and Related Algorithms 4.10 Divide-and-Conquer 4.11 Exercises 5 Graph Traversal 5.1 Flavors of Graphs 5.2 Data Structures for Graphs 5.3 War Story: I was a Victim of Moore's Law 5.4 War Story: Getting the Graph 5.5 Traversing a Graph 5.6 Breadth-First Search 5.7 Applications of Breadth-First Search 5.8 Depth-First Search 5.9 Applications of Depth-First Search 5.10 Depth-First Search on Directed Graphs 5.11 Exercises 6 Weighted Graph Algorithms 6.1 Minimum Spanning Trees 6.2 War Story: Nothing but Nets 6.3 Shortest Paths 6.4 Wax Story: Dialing for Documents 6.5 Network Flows and Bipartite Matching 6.6 Design Graphs, Not Algorithms 6.7 Exercises……
插图：3.7.2 Efficient String Matching via HashingStrings are sequences of characters where the order of the characters matters, sinceALGORITHM is different than LOGARITHM. Text strings are fundamental to ahost of computing applications, from programming language parsing/compilation,to web search engines, to biological sequence analysis.The primary data structure for representing strings is an array of characters.This allows us constant-time access to the ith character of the string. Some auxiliaryinformation must be maintained to mark the end of the string either a specialend-of-string character or （perhaps more usefully） a count of the n characters inthe string.The most fundamental operation on text strings is substring search, namely:Problem: Substring Pattern MatchingInput: A text string t and a pattern string p.Output: Does t contain the pattern p as a substring, and if so where？