# Introduction to string indexing

## Introduction

In this chapter we'll focus on different approaches used to index strings or collections of strings such that subsequent queries can be performed more efficiently. When discussing string matching in the context of the Z and KMP algorithms, the Z and sp values were a form of indexing, but the indices were constructed for each pattern separately. More specifically, assume you have a text $$T$$ of length $$n$$ and a pattern $$P\_1$$ of length $$m\_1$$. The run time required to find $$P\_1$$ inside $$T$$ is $$O(m\_1 + n)$$ for either the Z algorithm or KMP (if this doesn't make sense, please read the chapter again).

Now, let's assume we have *k* different patterns: $$P\_1,..., P\_k$$. If we try to search them against $$T$$, we incur a cost of $$O(m\_i + n)$$ for each pattern $$i$$, leading to a total runtime of $$O(nk + \sum\_i m\_i)$$ for all $$k$$ patterns. We can't easily avoid the second part of this cost ($$\sum\_i m\_i$$) as we have to look at every character in each pattern. But can we avoid going through the text $$k$$ times? The indexing approaches described in this chapter will help us do so, and also provide some additional useful functionality.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mpop.gitbook.io/bioinformatics-lecture-notes/string-indexing/introduction-to-string-indexing.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.