Manipulating Strings The length of the string Copy a stringReverse a stringConcatenate two strings Search a character in a string Search a string in a stringString matching problem (or string searchingproblem)
Manipulating Strings ⚫ The length of the string ⚫ Copy a string ⚫ Reverse a string ⚫ Concatenate two strings ⚫ Search a character in a string ⚫ Search a string in a string ⚫ String matching problem (or string searching problem)
String Matching Problem String matching algorithms are also used tosearch for particular patterns in DNAsequences. E.g., find the location of pattern P = abaa inthe text T = abcabaabcabac
String Matching Problem ⚫ String matching algorithms are also used to search for particular patterns in DNA sequences. ⚫ E.g., find the location of pattern P = abaa in the text T = abcabaabcabac
String Matching AlgorithmsGiven: text T with length n, pattern P with length mNaivealgorithmMatching time: O(n-m+1)m)Rabin-Karp algorithmPreprocessingtime:o(m)Matching time: O((n-m+1)m)Knuth-Morris-Pratt (or KMP) algorithmPreprocessing time: O(m)Matching time: @(n)Boyer-Moore (or BM) algorithmPreprocessing time: O(m)Matching time: worst @(n), average (n/m)
String Matching Algorithms ⚫ Given: text T with length n, pattern P with length m ⚫ Naïve algorithm ⚫ Matching time: O((n-m+1)m) ⚫ Rabin-Karp algorithm ⚫ Preprocessing time: (m) ⚫ Matching time: O((n-m+1)m) ⚫ Knuth-Morris-Pratt (or KMP) algorithm ⚫ Preprocessing time: (m) ⚫ Matching time: (n) ⚫ Boyer-Moore (or BM) algorithm ⚫ Preprocessing time: (m) ⚫ Matching time: worst (n), average (n/m)
C String Library Functions ctype.h and string.h#include<ctype.h>#include<string.h>int isalpha(int c);char *strcat(char *dst, const char *src);int isupper(int c);char*strncat(char *dst, const char *src, size_t n)int islower(int c);int strcmp(const char *s1, const char *s2);int isdigit(int c);int strncmp(const char *s1, const char *s2, size_t n);int ispunct(int c);char *strcpy(char *dst, const char *src);int isxdigit(int c);char *strncpy(char*dst, const char *src, size_t n);int isprint(int c);size_t strlen(const char *s);int toupper(int c);char*strstr(const char *s1, const char *s2);int tolower(int c);char*strtok(char *s1, const char *s2);
C String Library Functions ⚫ ctype.h and string.h #include <ctype.h> int isalpha(int c); int isupper(int c); int islower(int c); int isdigit(int c); int ispunct(int c); int isxdigit(int c); int isprint(int c); int toupper(int c); int tolower(int c); #include <string.h> char *strcat(char *dst, const char *src); char *strncat(char *dst, const char *src, size_t n); int strcmp(const char *s1, const char *s2); int strncmp(const char *s1, const char *s2, size_t n); char *strcpy(char *dst, const char *src); char *strncpy(char *dst, const char *src, size_t n); size_t strlen(const char *s); char *strstr(const char *s1, const char *s2); char *strtok(char *s1, const char *s2);
C++ String Library functionsC++ supports the c-style strings C++ also has a string classstring::size()string::empty0string::append(s)string::erase(n,m)string::insert(size_typen,conststring&s)string:find(s)string::rfind(s)
C++ String Library functions ⚫ C++ supports the c-style strings ⚫ C++ also has a string class string::size() string::empty() string::append(s) string::erase(n, m) string::insert(size_type n, const string&s) string::find(s) string::rfind(s)