Data Structure Chapter 4-String

The picture below is a mind map about strings, including the definition and implementation of strings and the pattern matching of strings, for your reference.

Edited at 2022-07-25 10:55:49

PlotWizard

Recent works View more works>>

Data Structure Chapter 4-String

PlotWizard

Recent works View more works>>

Recommended to you
Outline

string

Definition and implementation of string

string definition

A finite sequence composed of several characters, recorded as

substring (pattern string)

A subsequence consisting of any number of consecutive characters in a string

main string

a string containing substrings

string storage structure

Fixed length sequence representation

Fixed length array

Heap allocated storage representation

Dynamically allocate storage space

Blockchain storage representation

Linked list method

Basic string operations

StrAssign (&T, chars): assignment operation. Assign the string T to chars.

StrCopy (&T,S): Copy operation. String T is obtained by copying string s.

StrEmpty (S): Empty operation. If s is an empty string, it returns TRUE, otherwise it returns FALSE.

strCompare (S,T): comparison operation. If S>T, the return value is >0; if S=T, the return value is =0; if it is, the return value is <0.

StrLength(s): Find the string length. Returns the number of elements of string s.

Substring (&Sub, S,pos,len): Find substring. Use sub to return a substring of length len starting from the pos-th character of string s.

Concat (&T,S1,S2): Concatenate. Use T to return a new string formed by concatenating S1 and S2.

Index (S,T): Positioning operation. If there is a substring with the same value as string T in the main string s, return its value in the main string The position of the first occurrence in s; otherwise the function value is 0.

clearString (&S): Clear operation. Clear s to an empty string. · DestroyString (&S): Destroy string. Destroy the string s.

string pattern matching

Simple pattern matching (brute force matching algorithm)

KMP algorithm

Prefixes, suffixes and partial match values for strings

Prefix: all header substrings of the string except the last character

Suffix: all tail characters of the string except the first character

Partial match value: the longest equal prefix and suffix length of all prefixes and suffixes of the string

The basic idea

In the k-th comparison, if the j-th character of pattern P does not match the i-th character of target T, then search for the longest equal prefix in the sequence of 0~j-1 characters before pattern P. String p0p1~pk and suffix substring pj-k-1~pj-1

If such a prefix substring and suffix substring are found, the k-th character of pattern P is used in the next pass to align it with the last mismatched position i of target T, and the next match is continued.

If it cannot be found, let the starting bit of P and the i-th bit of target T continue to be aligned and compared.

Code

matching process