C++实现子串查找算法

该资源包含了两个查找子串的C语言程序示例，以及一个获取用户输入字符串的函数和一个将字符串转换为浮点数的函数。这些代码适用于初学者学习和理解基本的字符串操作。 首先，让我们详细分析第一个查找子串的程序（简称程序1）： ```c // 该程序采用KMP算法查找子串 #include<stdio.h> void main() { char *s="abcdefghijk", *t="def"; int i, j, k, m = -1; for(i=0; s[i]!='\0'; i++) { k = i; for(j=0; t[j]!='\0'&&s[k]!='\0'&&s[k++]==t[j]; j++); if(t[j]=='\0') { m = i; break; } } printf("%d\n", m); // 如果未找到子串，返回-1 } ``` 程序1使用了KMP（Knuth-Morris-Pratt）算法，它在主串`s`中查找子串`t`。KMP算法的特点是避免了不必要的字符比较，当匹配失败时，可以利用已知的匹配信息快速跳过部分主串。在这里，变量`k`保存了子串的当前位置，变量`i`表示主串的当前位置。内部的`for`循环用于比较子串和主串，如果匹配成功，`j`会增加，直到子串结束或不匹配发生。若子串`t`完全匹配，`m`会被更新为主串中子串开始的位置，并退出循环。 第二个查找子串的程序（简称程序2）： ```c // 该程序采用朴素的线性搜索方法查找子串 #include<stdio.h> void main() { char *s="abcdefghijk", *t="def"; int i=0, j=0, m=0; while(s[i]!='\0'&&t[j]!='\0') { if(s[i]==t[j]) { i++; j++; } else { m++; i = m; j = 0; } } if(t[j]!='\0') m = -1; printf("%d\n", m); } ``` 程序2使用了朴素的线性搜索方法，逐个比较主串`s`和子串`t`的字符。当字符匹配时，`i`和`j`都递增；当不匹配时，`i`向后移动一位，`j`重置回0，继续比较。如果遍历完子串但未找到匹配，返回-1。 接下来是获取用户输入字符串的函数`getlinestr()`： ```c #include<stdio.h> char* getlinestr() { char x, *p, *pok; int len=0; x=getchar(); p=new char('\0'); while(x!='\n') { len++; pok=new char[len+1]; strcpy(pok,p); pok[len-1]=x; pok[len]='\0'; delete[] p; p=pok; x=getchar(); } return pok; } ``` `getlinestr()`函数用于从标准输入读取一行字符，直到遇到换行符`\n`为止。使用动态内存分配创建一个新的字符串`pok`来存储输入，每次读取一个字符，都会更新字符串的长度并重新分配内存。 最后，是将字符串转换为浮点数的函数`strtof()`： ```c // 仅显示函数声明，具体实现通常由C++库提供 double strtof(char *p); ``` `strtof()`函数通常用于将表示浮点数的字符串转换为对应的浮点数值。在C++中，这个功能由标准库提供，不需要自行编写。 总结：这个资源提供了C语言中的字符串处理示例，包括使用KMP算法查找子串、朴素线性搜索查找子串、从标准输入获取字符串以及将字符串转换为浮点数的基本方法，对于学习C/C++语言的初学者来说非常有帮助。