【leetcode】Implement strStr()
2024-03-31 09:45:42
Implement strStr()
Implement strStr().
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
最简单的思路，逐一比较：
class Solution {
public:
int strStr(char *haystack, char *needle) {
int n1=strlen(haystack);
int n2=strlen(needle);
int result=-;
bool flag;
for(int i=;i<n1-n2+;i++)
{
flag=true;
for(int j=;j<n2;j++)
{
if(haystack[i+j]==needle[j])
{
continue;
}
else
{
flag=false;
break;
}
}
if(flag==true)
{
result=i;
break;
}
}
return result;
}
};
可以采用KMP算法：
KMP算法的核心是，当比较某两个字符不相等时，不必从头开始重新比较，而是根据引入的next，确定子串回溯的位置。
举个例子：
一个子串：
|
a
|
b |
a
|
a
|
b
|
a
|
b
|
a
|
|
-1
|
0
|
0
|
1
|
1
|
2
|
3
|
2
|
next[j]表示了如果在比较字符串时，needle[j]!=haystack[k]
那么下一次比较时，从next[j]所指定的位置进行比较，即j=next[j],k不变
class Solution {
public:
int strStr(char *haystack, char *needle) {
int i=;
int j=;
int n1=strlen(haystack);
int n2=strlen(needle);
vector<int> next=getNext(needle);
while(i<n1&&j<n2)
{
if(j==-||haystack[i]==needle[j])
{
i++;
j++;
}
else
{
j=next[j];
}
}
if(j==n2)
{
return i-j;
}
else
{
return -;
}
}
vector<int> getNext(char *needle)
{
int n=strlen(needle);
vector<int> next(n);
if(n==)
{
return next;
}
next[]=-;
int i=;
int k=-;
while(i<n-)
{
if(k==-||needle[k]==needle[i])
{
i++;
k++;
next[i]=k;
}
else
{
k=next[k];
}
}
return next;
}
};
对于k=next[k]
举个例子：如果比较最
|
a
|
b |
a
|
a
|
b
|
a
|
b
|
a
|
|
-1
|
0
|
0
|
1
|
1
|
2
|
3
|
2
|
最后一个元素的next为2
这是因为，倒数第二个元素与第四个元素不相等，此时
k=next[3]=1;
继续循环，
b==needle[k]=needle[1]
所以
i++
k++
得到
next[7]=2;
最新文章
- Linux C++ 开发简介
- android第一行代码－6.自定义控件的实现
- 天龙客户端的ResourceManager
- id to load is required for loading----id被要求加载exception
- AD15高版软件卡不卡，问题解决大讨论
- Python新手学习基础之数据结构-列表2 添加
- 搭建lamp环境Q&A
- PHP调试工具 《Kint》
- ActiveMQ消息队列介绍（转）
- PHPCMS V9{loop subcat(0,0,0,$siteid) $r}怎么解释？
- Hdu 3962 Microgene (AC自己主动机+矩阵)
- TCP/IP的那些事--子网掩码
- 对于单页应用中如何监听 URL 变化的思考
- 迅为iTOP-4418/6818开发板-驱动-IO初始化配置介绍和例程
- 关于虹软人脸识别SDK的接入
- Go To Oracle
- nginx配置url重写
- 获取指定tag的代码
- 在 Azure 上部署 Asp.NET Core Web App
- Spring容器是如何实现 Bean 自动注入（xml）