Implement strStr().
Returns a pointer to the first occurrence of needle in haystack, ornullif needle is not part of haystack.
经典的字符串查找问题了。这个问题其实有四种比较经典的算法,这里介绍2种半。因为这里的Boyer-Moore是简易版,全功率版应该是简易版加上KMP法的,那个实在是复杂,面试是不大可能写出来的,除非记熟了。
还有一种是Rabin-Karp fingerprint search,这个是利用hash函数产生所谓的fingerprint,然后对比子串的hash值和原串同样字符长的hash值是否一致,这个算法的关键是如何处理hash值。
下面的三种方法测试LeetCode的运行时间都差不多,大概是因为测试数据不大吧。
1 BF暴力法:
char *strStr(char *haystack, char *needle)
{
if (!haystack || !needle) return nullptr;
int n = strlen(haystack);
int m = strlen(needle);
for (int i = 0; i <= n - m; i++)
{
int j = 0;
for (; j < m; j++)
{
if (needle[j] != haystack[j+i]) break;
}
if (j == m) return haystack + i;
}
return nullptr;
}
3 简易版Boyer Moore法
void bmSkipTable(char *ch, vector<int> &skipTable)
{
if (!ch) return;
skipTable.resize(26);
int m = strlen(ch);
for (int i = 0; i < m; i++)
{
skipTable[ch[i] - 'a'] = i;
}
}
char *bmStrStr(char *haystack, char *needle)
{
if(!haystack || !needle) return haystack;
int n = strlen(haystack);
int m = strlen(needle);
vector<int> skipTable;
bmSkipTable(needle, skipTable);
int skip = 0;
for (int i = 0; i <= n-m; i+=skip)
{
skip = 0;
for (int j = m-1; j >= 0; j--)
{
if (haystack[i+j] != needle[j])
{
skip = j - skipTable[haystack[i+j] - 'a'];
if (skip < 1) skip = 1;
break;
}
}
if (skip == 0) return haystack + i;
}
return nullptr;
}
2 更新KMP法
//2014-2-20 update
char *strStr(char *hay, char *ne)
{
int len = strlen(hay);
int n = strlen(ne);
vector<int> tbl = genTbl(ne, n);
for (int i = 0, j = 0; i <= len - n; )//改成i<len那么会空串的时候出错
{
for ( ; j < len && j < n && hay[i+j] == ne[j]; j++);
if (j == n) return hay+i;
if (j > 0)
{
i += j - tbl[j-1] - 1;
j = tbl[j-1] + 1;
}
else i++;
}
return nullptr;
}
//修正bug
vector<int> genTbl(char *ne, int n)
{
vector<int> tbl(n, -1);
for (int i = 1, j = 0; i < n;)
{
if (ne[i] == ne[j])
{
tbl[i] = j;
++j;
++i;
}
else if (j > 0) j = tbl[j-1]+1;
else i++;
}
return tbl;
}
//2014-2-21 update Boyer-Moore Algorithm
char *strStr(char *hay, char *ne)
{
int n = strlen(ne);
if (n == 0) return hay;
int len = strlen(hay);
vector<int> tbl(256, -1);
for (int i = 0; i < n; i++)
{
tbl[ne[i]] = i;
}
for (int i = n-1, j = n-1; i < len; )
{
for ( ; j >= 0 && hay[i] == ne[j]; j--, i--);
if (j < 0) return hay + i + 1;
if (tbl[hay[i]] < j) i += n - tbl[hay[i]] - 1;
else i += n - j;
j = n-1;
}
return nullptr;
}
分享到:
相关推荐
leetcode实现strstr LeetCode 项目介绍 LeetCode刷题,记录自己刷题过程 目录 一、初级算法题 数组篇 序号 题目 类名 博客地址 1 从排序数组中删除重复项 2 买卖股票的最佳时机 II 3 旋转数组 4 存在重复元素 5 只...
leetcode实现strstr leetcode-cn.com use golang resolve problems in leetcode-cn.com 自己学习golang所写,可能有更简单,性能更好的可以pull requests一起学习够浪 每个源码都有简单的leetcode上所要求的测试 源...
leetcode-js 记录刷leetcode分析过程,希望一点点进步! leetcode地址 刷题顺序 按照顺序刷第一遍,记录实现思路,自己的优化方案,并研究高票大佬的思路。 已完成题目归档 序号 题目 题解 实现(初步思路/优化思路/...
题目地址:思路对于js来说就一行看解题思路使用 KMP 实现代码* @param {string} haystack* @param {string} need
# [LeetCode](https://leetcode.com/problemset/algorithms/) ![Language](https://img.shields.io/badge/language-Python%20%2F%20C++%2011-orange.svg) [![License]...
leetcode题库所有数据库问题 Leetcode 所有数据库问题:Leetcode 问题 Active-Businesses-LeetCode.png 活跃用户-LeetCode.png 活动-参与者-LeetCode.png 至少合作过三次的演员和导演-LeetCode.png Ads-Performance-...
哈希,众数,Boyer-Moore 217 简单 设置,排序,哈希 219 简单 哈希,滑动窗口 268 简单 数学,异或 283 简单 双指针 509 简单 867 简单 977 简单 双指针 1588 简单 动态规划,滑动窗口 2.链表 不。 标题 ...
leetcode 答案Leetcode---数据库 我对 Leetcode 数据库问题的回答
BM(Boyer-Moore)算法 31.下一个排列----巧计 32.(hard)最长有效括号----栈 33.搜索旋转排序数组----二分查找 34.在排序数组中查找元素的第一个和最后一个位置----二分查找 39.组合总和----回溯 42.(hard)接雨水-...
leetcode 跳跃 leetcode刷题笔记 005-2. 最长回文子串 字符串+中心扩散 :star:010-3. 正则表达式匹配 动态规划 019-2. 删除链表的倒数第N个节点 链表+快慢指针 022-2. 括号生成 回溯法 :star:031-2. 下一个排列 数组...
leetcode 溢价Leetcode-公司-问题-2020---2021- Leetcode Premium 公司问题按频率降序排列。 2021 年 3 月更新。
leetcode添加元素使和等于 LeetCode 数组 Leetcode 0004 寻找两个正序数组的中位数 ----> ----> Leetcode 0027 移除元素 ----> ----> Leetcode 0041 缺失的第一个正数 ----> ----> Leetcode 0048 ...
leetcode 296 LeetCode Summary 算法 1.确定有限状态机 - 解决多重If-else嵌套问题 - No8 & No65 2.弗洛伊德循环查找(快慢指针) - 解决链表是否存在环的问题 - No202 3.厄拉多塞筛法 - 快速算出质数的方法 - No204...
leetcode 答案解析 golang解答
leetcode-cheat 的发布 它是什么 ? 这是一个chrome 扩展,可以帮助您更高效地使用 leetcode。您可以从 重要: leetcode-cheat 现在只支持中文版。 也就是说不完全支持leetcode.com,但是你可以用leetcode-cn.com代替...
28-implement-strstr.c 知识管理计划(完成)和 Boyer-Moore 算法。 使用 manacher 算法更新 5-longest-palindromic-substring.c。 (完毕) 使用优化算法更新 214-shortest-palindrome.c。 使用二分搜索更新 287-...
leetcode-cli-plugins leetcode-cli 的第 3 方插件。 什么是 如何使用 如何使用 插件 名称 描述 增强的命令 按公司或标签过滤问题 list 不要在同一台计算机上使 Chrome 的会话过期 login 不要在同一台计算机上使 ...
leetcode中文版 Leetcode-Chinese-Version This repo contains Leetcode exercises in Python3 or Python2. 中文版leetcode题目及自己在做的题目,有些题目解答效率不高,还在练习。 Address:
leetcode-cli 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的网站! ⦙⦙⦙⦙⦙⦙⦙⦙ 一个很打问题的方法。 问题来缓解离线思考。 编码前的源代码。 居住和与 leetcode.com。 下载你...
Algorithm-LeetCode-Solution-From-GuaZiDou.zip,Leetcode解决方案Gitbook,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。