字符串简称串，计算机上的非数值处理的对象基本都是字符串类型的数据，串是由零个或多个字符组成的有限序列、
定义串的结构体，设定串的最大长度为MAXLEN的值，length用来记录串的长度。
#define MAXLEN 1000
typedef struct{
char ch[MAXLEN];
int length;
}SString;
创建一个串，为了让串与它的索引值对上，所以存储的时候浪费掉第一个位置（也就是ch[0]）的空间，为了防止直接pringf输出的时候报错，给串的第一个值设置为‘ ’，也就是直接输出不会报错，但是也不会有结果。
// 字符串下标从1开始记录，将ch[0]设置为‘ ’
SString createString(){
SString str;
str.ch[0] = ' ';
str.length = 0;
return str;
}
由于我们的串是从1开始记录的，因此用常规的printf进行输出得到的结果是不准确的，因此需要写一个函数来输出串。
void printString(SString str){
for (int i=1; i<=str.length; i++)
printf("%c", str.ch[i]);
printf("n");
}
字符串组c的值赋值给字符串str
void StrAssign(SString *str, char c[]){
str->length = 0;
for (int i=0; c[i]!=' '; i++)
str->ch[++str->length] = c[i];
}
拷贝字符串c中的内容到字符串str中
void StrCopy(SString *str, SString c){
str->length = 0;
for (int i=1; i<=c.length; i++)
str->ch[++str->length] = c.ch[i];
}
判断串str是否为空串只需要根据它的length值是否为0来确定。
int StrEmpty(SString str){
return str.length ? 0 : 1;
}
获取字符串str的长度
int StrLength(SString str){
return str.length;
}
清空字符串str，将str的内容设置为‘ ‘，并将字符串str的长度归零。
void ClearString(SString *str){
for (int i=1; str->ch[i]!=' '; i++)
str->ch[i] = ' ';
str->length = 0;
}
连接字符串t1和字符串t2的值，并把结果赋值给字符串str
void Concat(SString *str, SString t1, SString t2){
str->length = 0;
for (int i=1; i<=t1.length; i++)
str->ch[++str->length] = t1.ch[i];
for (int i=1; i<=t2.length; i++)
str->ch[++str->length] = t2.ch[i];
}
取字符串str从pos位置开始，长度为len的子串substr
void SubString(SString *substr, SString str, int pos, int len){
substr->length = 0;
for (int i=pos; ich[++substr->length] = str.ch[i];
}
比较两个串的大小，根据ascll码一位位对比。
int StrCompare(SString str1, SString str2){
int k = 1;
int f = 0; // f为1表示str1 > str2，f为0表示str1 = str2，f为-1表示str1 < str2
while (k <= str1.length && k <= str2.length){
if (int(str1.ch[k] - str2.ch[k]) > 0){
f = 1;
return f;
}
else if (int(str1.ch[k] - str2.ch[k]) < 0){
f = -1;
return f;
}
k++;
}
if (str1.length > str2.length) f = 1;
else if (str1.length < str2.length)f = -1;
return f;
}
获取子串下标索引，若substr不是str的子串则返回-1。
int Index(SString str, SString substr){
int pos = 0;
int f;
while (++pos <= (str.length - substr.length+1)){
int f = 1; // 1表示匹配成功
int k = pos; // 标记主串索引开始位置
for (int i=1; i<=substr.length; i++)
if (str.ch[k++] != substr.ch[i]){
f = 0;
break;
}
if (f == 1)
break;
}
return f ? pos : -1;
}
显然，这种每一位都进行对比的方式在算法是不够好的（有多次多余的对比操作），我们可以使用kmp算法进行优化，对于匹配失败的情况，我们并不是直接从头开始对比，而是根据子串的next[j]的值开始。
int KMP_Index(SString str, SString substr){
int i = 1, j = 1;
int next[substr.length+1];
get_next(substr, next);
while (i < (str.length - substr.length + 1)){
if (j == 0 || str.ch[i] == substr.ch[j]){
i++; j++;
}
else
j = next[j];
if (j > substr.length)
return i-j+1;
}
return -1;
}
不难发现，在使用kmp算法的时候我们需要数组next[]来进行辅助完成，因此我们就需要写一个函数来获取子串的next[]数组。若子串中有和头部相同且反复出现的部分则可以不用再从头开始检验。
void get_next(SString substr, int next[]){
int i = 1, j = 0;
next[1] = 0;
while (i < substr.length){
if (j == 0 || substr.ch[i] == substr.ch[j]){
i++; j++;
next[i] = j;
}
else j = next[j];
}
}
next[]可以进行进一步的优化，若在子串中遇到和索引较小的值相同的值的时候，可以将其next{]的值同样处理。第一种方法要配合get_next()函数一起使用，而下一种则是他们的结合体。
void get_better_next(SString substr, int next[]){
get_next(substr, next);
for (int i=2; i<=substr.length; i++){
if (substr.ch[i] = substr.ch[next[i]])
next[i] = next[next[i]];
}
}
void get_better_next(SString substr, int next[]){
int i = 1, j = 0;
next[1] = 0;
while (i < substr.length){
if (j == 0 || substr.ch[i] == substr.ch[j]){
i++; j++;
if (substr.ch[j] == substr.ch[next[j]])
next[i] = next[j];
else
next[i] = j;
}
else j = next[j];
}
}
最后，当然要写一个测试函数来确认我们上述函数功能的准确性啦！本来想要用time函数来比对一下index和kmp_index函数的运行时间到底优化了多少，结果发现串太短了，貌似没什么影响
void test(){
SString str = createString();
SString text = createString();
SString text2 = createString();
SString substr = createString();
char c[MAXLEN];
printf("please write string str: ");
gets(c);
StrAssign(&str, c);
printf("string str(%d) is: ", StrLength(str));
printString(str);
if (StrEmpty(str))
printf("str is an empty string!n");
printf("please write string text: ");
gets(c);
StrAssign(&text, c);
printf("string text(%d) is: ", StrLength(text));
printString(text);
StrCopy(&str, text);
printf("after copy string str(%d) is: ", StrLength(str));
printString(str);
printf("please write string text2: ");
gets(c);
StrAssign(&text2, c);
printf("string text2(%d) is: ", StrLength(text2));
printString(text2);
Concat(&str, text, text2);
printf("string str(%d) concatenates text and text2, the result is: ", str.length);
printString(str);
SubString(&substr, str, 2, 3);
printf("string substr(%d) is child string of str: ", substr.length);
printString(substr);
time_t t;
int start_t = time(&t);
int idx = Index(str, substr);
int end_t = time(&t);
if (idx != -1)
printf("(%d ms)string substr is in string str, and its index is from %d to %dn",
end_t - start_t, idx, idx+substr.length-1);
else
printf("(%d ms)string substr is not in string str!n", end_t - start_t);
start_t = time(&t);
int idx_kmp = KMP_Index(str, substr);
end_t = time(&t);
if (idx_kmp != -1)
printf("(%d ms)string substr is in string str, and its index is from %d to %dn",
end_t - start_t, idx_kmp, idx_kmp+substr.length-1);
else
printf("(%d ms)string substr is not in string str!n", end_t - start_t);
}
// 测试StrCompare函数，因为过长，所以分出另一个测试函数
void test2(){
printf("begin to test StrCompare:n");
SString str1 = createString();
SString str2 = createString();
char c[MAXLEN];
gets(c);
StrAssign(&str1, c);
gets(c);
StrAssign(&str2, c);
int rst = StrCompare(str1, str2);
if (rst == 1) printf("str1 > str2n");
else if (rst == 0) printf("str1 = str2n");
else printf("str1 < str2n");
}
测试结果如下图所示：
仅本人学习笔记，若有疑问，欢迎留言讨论！
