Data Structure
String
$Structure\rightarrow list$
- linked String
- Arrayed String
General Concepts of String
- $Null\ String(\emptyset)：Nothing\ in\ the\ string, the\ length\ is\ zero.$
- $Blank(Space)string：Only\ includes\ one\ or\ more\ blanks(spaces)in\ the\ string.$
- $Substring: sub-sequence\ of\ one\ string.$
ADT
{
ADT String {Data Object：D＝{ ai | ai∈CharacterSet,i=1,2,...n, n≥0 }
Data Relationship：R1＝{ < ai-1, ai > | ai-1, ai∈D,i=2,...,n }
Operation： ……
} ADT String
Operations
{
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
StrAssign (&T, chars) //string assignment
Initial：chars are character constant.
Output：assign chars to T.
StrCopy (&T, S) //String Copy
Initial：S string.
Output：Copy S string to T.
DestroyString (&S)
Initial：S String.
Output：Destroy S.
ClearString (&S)
Initial：S String.
Output：Change S into Null string.
StrEmpty (S)
Initial：S String.
Output：If S is null string，return TRUE，otherwise, return FALSE.
StrCompare (S, T) //String comparison
Initial：S and T Strings.
Output：If S>T，the return value is greater than 0；
if S=T，the return value is 0；
if S<T，the return value is less than 0.
StrLength (S) // get string length
Initial ：S String.
Output：The number of characters.
Concat(&T,S1,S2) //String Concatenation
Initial：String S1 and S2。
Output：Concatenate S1 and S2 and put the new string into T
SubString (&Sub, S, pos, len) //Get substring
Initial：String S，1 <= pos <= StrLength(S) and 0 <= len <= StrLength(S) - pos + 1
Output：Return substring of string, which from pos to pos + len - 1 position of S
Index (S, T, pos) //String index
Initial：String S and T，T is non-empty,1 <= pos <= StrLength(S)
Output: If the there is a substring T in S,
return the position of sub-string T occurs first time after pos, otherwise return 0.
Replace (&S, T, V) //String replacement
Initial：String S, T and V, T is non-empty.
Output：Replace non-overlapped substring T of S with V
StrInsert (&S, pos, T)
Initial：String S and T，1 <= pos <= StrLength(S) ＋ 1
Output：Insert String T before the pos character of string S
StrDelete (&S, pos, len)
Initial：String S ，1 <= pos <= StrLength(S) - len + 1
Output：Delete a sub-string with len length from pos character in string S.
|
}
The StrAssign,Strcopy,StrCompare,StrLength,Concat and SubString are called as Minimum Operation Set of string type.
That is, these operations can not be implemented with other string operations, But the other string operations can be implemented with these 6 basic string operations.
String Pattern Matching
ForceMatch
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
Rank ForceMatch(const String &P, const String &T) {
Rank n = T.length(), i = 0;
Rank m = P.length(), j = 0;
while (i < n && j < m) {
if (T[i] == P[j]) {
i++;
j++;
} else {
i -= j - 1;
j = 0;
}
}
return i - j;
}
|
$n = T.length(),and\ m = P.length(), T=O(mn)$
KMP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
int *BuildNext(const String &P) {
Rank m = P.length();
int *N = new int[m]{};
int t = -1, j = 0;
N[0] = -1;
while (j < m - 1)
(t < 0 || P[j] == P[t]) ? N[++j] = ++t : t = N[t];
return N;
}
Rank KMPFirst(const String &P, const String &T) {
int *next = BuildNext(P);
Rank n = T.length(), i = 0;
Rank m = P.length(), j = 0;
while (i < n && j < m) {
if (j < 0 || T[i] == P[j]) {
i++;
j++;
} else
j = next[j];
}
delete[]next;
return i - j;
}
|
$n = T.length(),and\ m = P.length(), T=O(m+n)$
Optimization KMP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
int *buildNext(const String &P) {
Rank m = P.length();
int *N = new int[m]{};
int t = -1, j = 0;
N[0] = -1;
while (j < m - 1) {
if (t < 0 || P[j] == P[t]) {
j++;
t++;
N[j] = P[j] == P[t] ? N[t] : t;
} else
t = N[t];
}
return N;
}
Rank KMPEnd(const String &P, const String &T) {
int *next = buildNext(P);
Rank n = T.length(), i = 0;
Rank m = P.length(), j = 0;
while (i < n && j < m) {
if (j < 0 || T[i] == P[j]) {
i++;
j++;
} else
j = next[j];
}
delete[]next;
return i - j;
}
|
supplement
for ppt use python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
def KMP(Str: str):
length = len(Str)
Next = [0 for _ in range(length)]
j, t = 0, -1
Next[0] = -1
while j < length - 1:
if t < 0 or Str[j] == Str[t]:
j = j + 1
t = t + 1
Next[j] = t
else:
t = Next[t]
Next = list(map(lambda k: k + 1, Next))
return Next
|
in list
1
2
3
4
5
6
7
8
9
10
11
12
|
def KMP(Str: list):
_size = len(Str)
Next = [0 for _ in range(_size)]
j, t = 1, 0
while j < Str[0]:
if t == 0 or Str[j] == Str[t]:
t = t + 1
j = j + 1
Next[j] = t
else:
t = Next[t]
return Next
|