• Strings
• Pattern Matching
• Complexity Analysis

❖ Strings

A string is a sequence of symbols.

An alphabet Σ is the set of possible symbols in strings.

Examples of strings:

• C program,   HTML document,   PDF document
• DNA sequence,   Digitized image,   Video (mp4)

Examples of alphabets:

• ASCII (1-byte chars),   Unicode (multi-byte chars)
• {0,1} (bits),   {0..9} (digits),   {A,C,G,T} (genome sequences)

Often, the "symbols" are letters (so we call them characters from now on)

❖ ... Strings

Notation:

• length(P) … #characters in P
• λ … empty string   (length(λ) = 0)    λω = ω = ωλ
• Σ^m … set of all strings of length m  over alphabet Σ
• Σ^* … set of all strings over alphabet Σ
• νω denotes the concatenation of strings ν and ω
• substring of P … any string Q such that P = νQω, for some ν,ω∈Σ^*
• prefix of P … any string Q such that P = Qω, for some ω∈Σ^*
• suffix of P … any string Q such that P = ωQ, for some ω∈Σ^*

❖ ... Strings

Example ...

The string  a/a  of length 3 over the ASCII alphabet has

• 4 prefixes:   ""    "a"    "a/"    "a/a"
• 4 suffixes:   "a/a"    "/a"    "a"    ""
• 6 substrings:   ""    "a"    "/"    "a/"    "/a"    "a/a"

Note:   "" means the same as λ   (= empty string)

❖ ... Strings

ASCII (American Standard Code for Information Interchange)

• Specifies mapping of 128 characters to integers 0..127
• The characters encoded include:
  • letters: A-Z and a-z,   digits: 0-9,   punctuation symbols
  • special non-printing characters: e.g. newline and space

Often, the character with ascii code 0 is called "NUL" rather than "NULL"

❖ ... Strings

Reminder ...

In C, a string is an array of chars (bytes) containing ASCII codes

• these arrays have an extra value at the end containing a 0 byte
• the extra 0 can also be written '\0'   (null character or null-terminator)
• convenient because don't have to track the length of the string

Because strings are so common, C provides convenient syntax:

char str[] = "hello";
// same as 
char str[] = {'h', 'e', 'l', 'l', 'o', '\0'};

Note: str[] will have 6 elements either way

❖ ... Strings

C provides string manipulation functions via #include <string.h>

Examples:

// return length of string
int strlen(char *str)
// copy one string into a string buffer
char *strcpy(char *dest, char *src)
// make a copy of a string (uses malloc())
char *strdup(char *)
// concatenate two strings, into buffer holding dest
char *strcat(char *dest, char *src)
// find substring pat inside string str
char *strstr(char *str, char *pat)
// copy at most n chars from src into a dest buffer
char *strncpy(char *dest, char *src, int n)

❖ ... Strings

Details of one #include <string.h> function ...

char *strncat(char *dest, char *src, int n)

• appends string src to the end of dest
• overwrites the '\0' at the end of dest
• adds terminating '\0' to result string
• assumes dest[] is large enough to hold all of above
• returns start of string dest
• will never add more than n characters
  • if strlen(src) less than n pad with '\0' characters
  • otherwise, dest is not null-terminated

❖ Pattern Matching

strstr() provides a simple example of string matching

The general string matching (aka pattern matching) problem

• given a string T  and a pattern P
• find occurences of P  in T
  • index of first occurence (or -1 if no occurences), or
  • pointer to first occurence (or NULL if no occurences, or
  • array of indexes/pointers to all occurences

strstr(str,pat) returns pointer to first occurence of pat in str

T  is sometimes called "haystack", P  is sometimes called "needle"

Note that regular expression pattern matching is quite a different beast.

❖ ... Pattern Matching

Example of simple (brute force) pattern matching:

❖ ... Pattern Matching

Brute-force pattern matching algorithm:

BruteForceMatch(T,P):
|  Input  text T of length n, pattern P of length m
|  Output starting index of a substring of T equal to P
|         -1 if no such substring exists
|
|  for all i = 0..n-m do
|  |  j = 0                       // check from left to right
|  |  while j<m ∧ T[i+j]=P[j] do  // test ith shift of pattern
|  |     j = j+1
|  |     if j=m then
|  |        return i              // entire pattern checked
|  |     end if
|  |  end while
|  end for
|  return -1                      // no match found

❖ ... Pattern Matching

C version of above algorithm:

int bruteForce(char *t, char *p)
{
   int n = strlen(t);  //length of string
   int m = strlen(p);  //length of pattern
   // for each starting position of pattern
   for (int i = 0; i <= n-m; i++) {
      // scan pattern, comparing against string
      for (int j = 0; j < m; j++) {
         // mismatch detected, terminate scan
         if (T[i+j] != P[j]) break;
      }
      // if reached end of pattern, have a match
      if (j == m) return i;
   }
   return -1;  // no match
}

❖ Complexity Analysis

Brute-force pattern matching runs in O(n·m)

• considers n-m starting positions for pattern
• from each starting position, scans up to m  chars in the pattern

Examples of worst case (forward checking):

• T = aaa … aaah
• P = aaah
• may occur in DNA sequences
• unlikely in English text