字符串的实现可以用数组也可以用链表。这里只讨论数组存储表示。

#实现

数组空间放满时，重新分配空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdlib.h>
void overflowProcess() {
	char *newAddress = new char[2 * maxSize];
	if (newAddress == NULL) {
		cerr << "Memory Allocation Error" << endl;
		exit(1);
	}
	
	int n = maxSize = 2 * maxSize;
	char *srcptr = ch;
	char *destptr = newAddress;
	while (n --) {
		*destptr ++ = *srcptr ++;
	}
	delete []ch;
	ch = newAddress;
}

串构造函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
AString::AString(int sz) {
	maxSize = n;
	ch = new char[maxSize + 1];
	if (ch == NULL) {
		cerr << "Allocation Error" << endl;
		exit(1);
	}
	curLength = 0;
	ch[0] = '\0';
};
AString::AString(const char *init) {
	int len = strlen(init);
	maxSize = (len > defaultSize) ? len : defaultSize;
	ch = new char[maxSize + 1];
	if (ch == NULL) {
		cerr << "Allocation Error" << endl;
		exit(1);
	}
	curLength = len;
	strcpy(ch, init);
};

串复制构造函数。

1
2
3
4
5
6
7
8
9
10
AString::AString(const AString& ob) {
	maxSize = ob.maxSize;
	ch = new char[maxSize + 1];
	if (ch == NULL) {
		cerr << "Allocation Error" << endl;
		exit(1);
	}
	curLength = ob.curLength;
	strcpy(ch. ob.ch);
};

求子串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
AString AString::operator () (int pos, int len) {
	AString temp;
	if (pos < 0 || pos + len - 1 >= maxSize || len < 0) {
		temp.curLength = 0;
		temp.ch[0] = '\0';
	} else {
		if (pos + len - 1 >= curLength) {
			len = curLength - pos;
		}
		temp.curLength = len;
		for (int i = 0, j = pos; i < len; i ++, j ++) {
			temp.ch[i] = ch[j];
		}
		temp.ch[len] = '\0';
	}
	return temp;
};

串赋值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
AString& AString::operator = (const AString& ob) {
	if (&ob != this) {
		delete []ch;
		ch = new char[maxSize + 1];
		if (ch == NULL) {
			cerr << "Allocation Error" << endl;
			exit(1);
		}
		curLength = ob.curLength;
		strcpy(ch, ob.ch);
	} else {
		cout << "String Assign Error" << endl;
	}
	return this;
}

串连接。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
AString& AString::operator += (const AString& ob) {
	char *temp = ch;
	int n = curLength + ob.curLength;
	int m = (maxSize >= n) ? maxSize : n;
	ch = new char[m];
	if (ch == NULL) {
		cerr << "Allocation Error" << endl;
		exit(1);
	}
	maxSize = m;
	curLength = m;
	strcpy(ch, temp);
	strcat(ch, ob.ch);
	delete []temp;
	return this;
}

#模式匹配

##B-F算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int AString::Find(AString& pat, int k) const {
	int i, j;
	for (i = k; i <= curLength - pat.curLength; i ++) {
		for (j = 0; j < pat.curLength; j ++) {
			if (ch[i + j] != pat.ch[j]) {
				break;
			}
		}
		if (j == pat.curLength) {
			return i;
		}
	}
	return -1;
};

##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
31
32
int AString::fastFind(AString& pat, int k, int next[]) const {
	int posP = 0, posT = k;
	int lengthP = pat.curLength;
	int lengthT = curLength;
	while (posP < lengthP && posT < lengthT) {
		if (posP == -1 || pat.ch[posP] == ch[posT]) {
			posP ++;
			posT ++;
		} else {
			posP = next[posP];
		}
	}
	if (posP < lengthP) {
		return -1;
	} else {
		return posT - lengthP;
	}
};
void AString::getNext(int next[]) {
	int j = 0, k = -1, lengthP = curLength;
	next[0] = -1;
	while (j < lengthP) {
		if (k == -1 || ch[j] == ch[k]) {
			j ++;
			k ++;
			next[j] = k;
		} else {
			k = next[k];
		}
	}
};