p. 438 · PDF 448

2 - 4 Other Algorithms

2-4-1 Character String Processing

Character string processing is an algorithm that uses characters as the elements of an array. String pattern matching is the main string processing that searches for the target character string from the character strings that are recorded in the array. The basic concept is the same as when numerical values are recorded in the elements of an array. However, since the target value is a character string, it must be confirmed whether multiple elements simultaneously match or not. The easiest concept of string pattern matching is the method of matching a substring (i.e., string that has the same number of characters as the target string) in array elements while one character is shifted from the first at a time.

Enlarge original visual

Original source text

1) Compare the target string with the substring that is located at the first in array 
elements. 
Subject string 
A 
B 
D
A
A
B
C
A
C
C 
↑ 
↑ 
↑
Target string 
A 
B 
C
2) When the substring does not match, compare after the starting position is shifted by 
one character. 
Subject string 
A 
B 
D
A
A
B
C
A
C
C 
↑ 
↑
↑
Target string 
A 
B
C

Source visual description

Original Other Algorithms source layout. Source labels: 1) Compare the target string with the substring that is located at the first in array; elements.; Subject string; A; B.

While this procedure is correct, efficiency is not very good. Therefore, the following Boyer-Moore method was proposed as an effective matching technique of character strings.

p. 439 · PDF 449

Enlarge original visual

Original source text

1) Compare the target string with the substring that is located at the first in array 
elements. 
Subject string 
A 
B 
D
A
A
B
C
A
C
C
↑ 
↑ 
↑
Target string 
A 
B 
C
2) When the tail character of the substring does not exist in the target string, make a 
comparison after the starting position is shifted by the number of characters in the 
target string. 
Subject string 
A 
B 
D
A
A
B
C
A
C
C 
↑
↑
↑
Target string
A
B
C
3) When the tail character of the substring exists in the target string, make a comparison 
by shifting the starting position so that the position of the tail character is matched 
with the position of the corresponding character in the target string. 
Subject string 
A 
B 
D
A
A
B
C
A
C
C 
↑
↑
↑
Target string
A
B
C

Source visual description

Original Other Algorithms source layout. Source labels: 1) Compare the target string with the substring that is located at the first in array; elements.; Subject string; A; B.

Other than this string pattern matching, the string process includes compression/decompression algorithms of strings, such as the run length method.