备考首页> 数据结构> 字符串
60

编程题 60 /85

实现函数 strStr。
函数声明如下：
char *strStr(char *str, char *dest)
返回一个指针，指向dest第一次在str中出现的位置，如果dest不是str的子串，则返回null

参考答案

普通想法, 枚举字符串的起点, 从每一个起点开始进行逐字符匹配. KMP 算法, 先利用动态规划的思想计算 next 数组, 然后在逐字匹配的过程中每次匹配失败时根据 next 数组在失败位置指定的回跳位置继续匹配下一个字符. next 数组中每一位表示从最开始到当前位置的子字符串的最大相同前后缀的长度, 可以使用动态规划计算
纠错 收藏
查看讨论
上一题 下一题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号