串，即字符串，用单引号或双引号表示的一组字符序列
子串包含于主串。
对串的主要操作如下：
1.获取某个子串在主串中的起始位置
2.获取主串的长度
3.获取从第index位置开始的字符后的子串位置
4.复制主串
5.赋值字串
6.比较两个字串的大小
串的两种实现方法：
顺序方式实现（静态存储和动态存储），链式方式实现(这种方式实现的串需要用malloc函数申请存储空间，同时在销毁时，调用free函数)
串的操作
- 定义
这里注意，结构体中的str字符数组是从1开始存字符的。
typedef struct {
int length;//表示串的长度
char str[MAXSIZE];//静态字符数组，存储串，可采用废弃第一个字符位置，这样为了保持在查找某一处字串时能够和其在主串的位置匹配
} String;
void initString(String &s) {
s.length = 0;
}
- 比较大小
//两个字符串比较大小，每个位置一个字符一个字符的比较，如果两个字符不一致，则返回 s1[i] - s2[i] 即可 ， 减号做ASCII码的运算。
//如果以较小的字符比较完了，还没有比较出来谁大谁小，则直接返回s1.length - s2.length即可，也就是说，长度长的那个大
//如果返回正数，s1比s2大，0 s1等于s2，小于0则s1小于s2
int compare(String s1, String s2) {//TODO 由于字符串是从char数组下标1开始，所以一定注意：在比较字符串时，从下标1开始获取字符一个一个比较
for (int i = 1; i <= s1.length && i <= s2.length; ++i) {
char s1str = s1.str[i];
char s2str = s2.str[i];
if (s1str != s2str) {
return s1str - s2str;
}
}
return s1.length - s2.length;
}
- 获取某个子串在主串中的起始位置
这里注意，在取主串中某几个连续字符与字串比较时，字串的下标时固定的，例如字串的长度是3，那么字串的下标就是固定的1,2,3.
//获取字串s2在主串s1的起始位置，如果未找到，则返回0
int indexOf(String s1, String s2) {
if (s2.length > s1.length) {
return 0;
}
int s2Len = s2.length;//获取s2的长度
printf(" %d n", s2Len );
for (int i = 1; i <= s1.length; ++i) {
//判断从i处位置加上s2Len长度的字符是否等于s1在i到i+s2Len处的子串
int size = i + s2Len;
if (size > s1.length) {
printf(" %s n", "444" );
return 0;//如果超过了主串的长度，则说明主串剩余的长度小于子串的长度，则返回0
}
// printf(" %c%c%c , %c%c%c n", s1.str[i], );
bool equals = true;
int s2Index = 1;
for (int j = i; j < size; j++) {
//依次取出主串和子在j处的字符进行比较，有一个不符合，则i++，全部符合则返回当前i的值
char s1Char = s1.str[j];
char s2Char = s2.str[s2Index];
if ((s1Char - s2Char) != 0) {
//不匹配
equals = false;
break;
}
s2Index++;
}
if (equals) {
return i;
}
}
return 0;
}
- 追加字符串
//追加str，也可以看作赋值操作
void appendStr(String &s, char *str) {
for (int i = 0; str[i] != ' '; i++) {
s.str[++s.length] = str[i];
}
}
- 获取某个主串从第i处开始的后j的字符
//获取某个字符串的子串
String getSubString(String s,int start,int length){
String substring;
initString(substring);
if(start + length > s.length ){
return substring;
}
for (int i = start; i < start + length; ++i) {
//赋值字符串
substring.str[++substring.length] = s.str[i];
}
return substring;
}
完整使用示例
#include "stdio.h" #include "malloc.h" #include串匹配算法#define MAXSIZE 255 typedef struct { int length;//表示串的长度 char str[MAXSIZE];//静态字符数组，存储串，可采用废弃第一个字符位置，这样为了保持在查找某一处字串时能够和其在主串的位置匹配 } String; void initString(String &s) { s.length = 0; } //追加str，也可以看作赋值操作 void appendStr(String &s, char *str) { for (int i = 0; str[i] != ' '; i++) { s.str[++s.length] = str[i]; } } //两个字符串比较大小，每个位置一个字符一个字符的比较，如果两个字符不一致，则返回 s1[i] - s2[i] 即可 ， 减号做ASCII码的运算。 //如果以较小的字符比较完了，还没有比较出来谁大谁小，则直接返回s1.length - s2.length即可，也就是说，长度长的那个大 //如果返回正数，s1比s2大，0 s1等于s2，小于0则s1小于s2 int compare(String s1, String s2) {//TODO 由于字符串是从char数组下标1开始，所以一定注意：在比较字符串时，从下标1开始获取字符一个一个比较 for (int i = 1; i <= s1.length && i <= s2.length; ++i) { char s1str = s1.str[i]; char s2str = s2.str[i]; if (s1str != s2str) { return s1str - s2str; } } return s1.length - s2.length; } //获取字串s2在主串s1的起始位置，如果未找到，则返回0 int indexOf(String s1, String s2) { if (s2.length > s1.length) { return 0; } int s2Len = s2.length;//获取s2的长度 printf(" %d n", s2Len ); for (int i = 1; i <= s1.length; ++i) { //判断从i处位置加上s2Len长度的字符是否等于s1在i到i+s2Len处的子串 int size = i + s2Len; if (size > s1.length) { printf(" %s n", "444" ); return 0;//如果超过了主串的长度，则说明主串剩余的长度小于子串的长度，则返回0 } // printf(" %c%c%c , %c%c%c n", s1.str[i], ); bool equals = true; int s2Index = 1; for (int j = i; j < size; j++) { //依次取出主串和子在j处的字符进行比较，有一个不符合，则i++，全部符合则返回当前i的值 char s1Char = s1.str[j]; char s2Char = s2.str[s2Index]; if ((s1Char - s2Char) != 0) { //不匹配 equals = false; break; } s2Index++; } if (equals) { return i; } } return 0; } //获取某个字符串的子串 String getSubString(String s,int start,int length){ String substring; initString(substring); if(start + length > s.length ){ return substring; } for (int i = start; i < start + length; ++i) { //赋值字符串 substring.str[++substring.length] = s.str[i]; } return substring; } int main() { //定义字符串s1 String s1; //初始化字符串s1 initString(s1); //定义字符串s2 String s2; //初始化字符串s2 initString(s2); //s1追加字符串 char s1str[] = "hello world abc 111 723"; appendStr(s1, s1str); printf(" %s n", s1.str ); //s2追加字符串 char s2str[] = "hello world abc 111 8"; appendStr(s2, s2str); //判断字符串是否为空 printf(" s1 is Empty %d n", s1.length == 0); printf(" s2 is Empty %d n", s2.length == 0); //比较两个字符串的大小 printf(" s1 compare s2 %d n", compare(s1, s2)); //获取某个子串在字符串中的首次出现的首字符的位置 //定义一个字串 char s3str[] = "abc"; String s3; initString(s3); //追加字符串 appendStr(s3, s3str); int index = indexOf(s1, s3); //获取子串s3在主串s1处的位置 printf(" first index position : %d n", index); //获取某个字符串从第i处位置开始的后j个子串 String substring = getSubString(s1,3,5);//获取s1从第三个字符位置开始的后5个字符 for (int i = 1; i <= substring.length; ++i) { printf("%c", substring.str[i] ); } return 0; }
- 朴素模式匹配算法
在长度为n的主串，长度为m的子串最多有 n-m+1个，最坏的时间复杂度为o(nm),最坏的情况无非就是遍历到最后一个子串时才和模式串匹配，那么此时相当于遍历了 （n-m+1）次，而每次又循环匹配了m次，所以此时的时间复杂度就是 (n-m+1)*m =
nm - m2 + m = O(nm),为什么最后等于nm，因为 通常主串的长度是远远大于模式串的。
朴素算法完整实现如下：
#include "stdio.h" #include "malloc.h" #include#define MAXSIZE 255 typedef struct { int length;//表示串的长度 char str[MAXSIZE];//静态字符数组，存储串，可采用废弃第一个字符位置，这样为了保持在查找某一处字串时能够和其在主串的位置匹配 } String; void initString(String &s) { s.length = 0; } //追加str，也可以看作赋值操作 void appendStr(String &s, char *str) { for (int i = 0; str[i] != ' '; i++) { s.str[++s.length] = str[i]; } } //两个字符串比较大小，每个位置一个字符一个字符的比较，如果两个字符不一致，则返回 s1[i] - s2[i] 即可 ， 减号做ASCII码的运算。 //如果以较小的字符比较完了，还没有比较出来谁大谁小，则直接返回s1.length - s2.length即可，也就是说，长度长的那个大 //如果返回正数，s1比s2大，0 s1等于s2，小于0则s1小于s2 int compare(String s1, String s2) {//TODO 由于字符串是从char数组下标1开始，所以一定注意：在比较字符串时，从下标1开始获取字符一个一个比较 for (int i = 1; i <= s1.length && i <= s2.length; ++i) { char s1str = s1.str[i]; char s2str = s2.str[i]; if (s1str != s2str) { return s1str - s2str; } } return s1.length - s2.length; } //获取字串s2在主串s1的起始位置，如果未找到，则返回0 int indexOf(String s1, String s2) { if (s2.length > s1.length) { return 0; } int s2Len = s2.length;//获取s2的长度 printf(" %d n", s2Len); for (int i = 1; i <= s1.length; ++i) { //判断从i处位置加上s2Len长度的字符是否等于s1在i到i+s2Len处的子串 int size = i + s2Len; if (size > s1.length) { printf(" %s n", "444"); return 0;//如果超过了主串的长度，则说明主串剩余的长度小于子串的长度，则返回0 } // printf(" %c%c%c , %c%c%c n", s1.str[i], ); bool equals = true; int s2Index = 1; for (int j = i; j < size; j++) { //依次取出主串和子在j处的字符进行比较，有一个不符合，则i++，全部符合则返回当前i的值 char s1Char = s1.str[j]; char s2Char = s2.str[s2Index]; if ((s1Char - s2Char) != 0) { //不匹配 equals = false; break; } s2Index++; } if (equals) { return i; } } return 0; } //获取某个字符串的字串 String getSubString(String s, int start, int length) { String substring; initString(substring); if (start + length > s.length) { return substring; } for (int i = start; i < start + length; ++i) { //赋值字符串 substring.str[++substring.length] = s.str[i]; } return substring; } //朴素模式匹配算法 int puSuIndexOf(String s1, String s2) { int s1Len = s1.length; int s2Len = s2.length; if (s2.length > s1.length) { return 0;//未找到 } //长度为n的主串最多包含长度为m的主串有 (n-m) + 1 个 int totalSubString = s1Len - s2Len + 1; int i = 1; while (i <= totalSubString) { //获取主串中从i位置开始后的s2Len个元素 String substr = getSubString(s1, i, s2Len); int result = compare(s2, substr);//模式串和子串进行比较 if (result == 0) { return i; } else { i++; } } return 0; } int main() { //定义字符串s1 String s1; //初始化字符串s1 initString(s1); //定义字符串s2 String s2; //初始化字符串s2 initString(s2); //s1追加字符串 char s1str[] = "hello world abc 111 723"; appendStr(s1, s1str); //s2追加字符串 char s2str[] = "abc"; appendStr(s2, s2str); //朴素模式匹配算法模式串 int index = puSuIndexOf(s, s2); printf(" %d n", index); return 0; }
