宝安专业网站设计多少钱建站好用的软件

宝安专业网站设计多少钱,建站好用的软件,做网站和百度推广有什么不一样,外贸网络推广经验一、题目描述给你两个字符串 haystack 和 needle #xff0c;请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标#xff08;下标从 0 开始#xff09;。如果 needle 不是 haystack 的一部分#xff0c;则返回 -1 。示例 1输入#xff1a;haystack s…一、题目描述给你两个字符串haystack和needle请你在haystack字符串中找出needle字符串的第一个匹配项的下标下标从 0 开始。如果needle不是haystack的一部分则返回-1。示例 1输入haystack sadbutsad, needle sad 输出0 解释sad 在下标 0 和 6 处匹配第一个匹配项的下标是 0。示例 2输入haystack leetcode, needle leeto 输出-1 解释leeto 没有在 leetcode 中出现。提示1 haystack.length, needle.length 10^4haystack和needle仅由小写英文字母组成二、解法一暴力匹配Brute Force思路最直接的方法就是从 haystack 的每个位置开始匹配 needle。步骤遍历haystack以当前位置作为起点逐个字符和needle比较如果全部匹配成功返回当前下标如果不匹配继续下一个位置C语言实现int strStr(char* haystack, char* needle) { int i 0; while (haystack[i] ! \0) { int j 0; while (needle[j] ! \0 haystack[i j] needle[j]) { j; } if (needle[j] \0) { return i; } i; } return -1; }复杂度分析复杂度结果时间复杂度O(n × m)空间复杂度O(1)其中n haystack 长度m needle 长度三、解法二使用C语言库函数strstrC 标准库提供了字符串查找函数strstr可以直接找到子串。思路使用strstr(haystack, needle)如果返回NULL说明没有找到否则返回指针差值C语言实现#include string.h int strStr(char* haystack, char* needle) { char* pos strstr(haystack, needle); if (pos NULL) { return -1; } return pos - haystack; }复杂度分析复杂度结果时间复杂度O(n × m)空间复杂度O(1)优点代码最简单实际开发中经常使用缺点面试通常不允许使用库函数四、解法三KMP算法字符串匹配经典算法KMPKnuth-Morris-Pratt算法是一种高效的字符串匹配算法。核心思想当发生不匹配时利用已经匹配的信息避免重复比较。普通算法主串回退KMP主串不回退 模式串根据 next 数组跳转五、构造 next 数组next[i]表示pattern[0..i-1] 的最长相同前后缀长度示例pattern ababaca index 0 1 2 3 4 5 6 char a b a b a c a next -1 0 0 1 2 3 0六、KMP完整代码C语言#include stdlib.h #include string.h int* getNext(char* pattern, int m) { int *next (int*)malloc(sizeof(int) * m); next[0] -1; int i 0; int j -1; while (i m - 1) { if (j -1 || pattern[i] pattern[j]) { i; j; next[i] j; } else { j next[j]; } } return next; } int strStr(char* haystack, char* needle) { if (needle[0] \0) return 0; int n strlen(haystack); int m strlen(needle); int *next getNext(needle, m); int i 0, j 0; while (i n j m) { if (j -1 || haystack[i] needle[j]) { i; j; } else { j next[j]; } } free(next); if (j m) return i - m; return -1; }七、KMP算法复杂度复杂度结果时间复杂度O(n m)空间复杂度O(m)其中n haystack长度 m needle长度八、三种解法对比解法时间复杂度特点暴力匹配O(n × m)简单易懂strstr函数O(n × m)实际开发常用KMP算法O(n m)面试高频算法九、总结本题本质是字符串匹配问题常见有三种解法1️⃣暴力匹配思路简单容易实现2️⃣库函数 strstr实际开发常用面试一般不允许3️⃣KMP算法字符串匹配经典算法时间复杂度O(n m)面试高频考点因此在面试中建议先写暴力解法 再优化为 KMP 算法这样能够体现完整的算法思路。