By Jalan
文章目录
**By Jalan**知识工具需求数学数据结构和算法语言
题干输入条件输出条件例子例1输入输出
例2输入输出
例3输入输出
题解第一次思路预期时间复杂度编写用时代码CPP运行用时
结尾
知识工具需求
数学
数据结构和算法
kmp算法
语言
题干
实现 strStr() 函数。 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
输入条件
输出条件
例子
例1
输入
haystack = "hello", needle = "ll"
输出
2
例2
输入
haystack = "aaaaa", needle = "bba"
输出
-1
例3
输入
haystack = "", needle = ""
输出
0
题解
第一次
思路
写个KMP把…注意在输入的时候对空的串进行操作.
预期时间复杂度
编写用时
20分钟
代码
CPP
#include <bits/stdc++.h>
#include <vector>
using namespace std
;
string haystack
;
string needle
;
class Solution
{
public:
void initiate(vector
<int> &prefixTable
, string pattern
)
{
prefixTable
.resize(pattern
.size());
}
void buildPrefixTable(vector
<int> &prefixTable
, string pattern
)
{
int j
= 1;
int len
= 0;
int size
= pattern
.size();
prefixTable
[0] = 0;
while (j
< size
)
{
if (pattern
[j
] == pattern
[len
])
{
len
++;
prefixTable
[j
] = len
;
j
++;
}
else
{
if (len
!= 0)
{
len
= prefixTable
[len
- 1];
}
else
{
prefixTable
[j
] = 0;
j
++;
len
= 0;
}
}
}
}
void moveTable(vector
<int> &prefixTable
)
{
int size
= prefixTable
.size();
for (int j
= size
- 1; j
>= 1; j
--)
{
prefixTable
[j
] = prefixTable
[j
- 1];
}
prefixTable
[0] = -1;
}
int search(string target
, string pattern
, vector
<int> prefixTable
)
{
int i
= 0;
int j
= 0;
while (i
< target
.size())
{
if (target
[i
] == pattern
[j
])
{
i
++;
j
++;
if (j
== pattern
.size())
{
return i
- pattern
.size();
}
}
else
{
j
= prefixTable
[j
];
if (j
== -1)
{
i
++;
j
= 0;
}
}
}
return -1;
}
int strStr(string haystack
, string needle
)
{
if (haystack
.size()==0&&needle
.size()==0)
{
return 0;
}
if (haystack
.size()==0||needle
.size()==0)
{
return -1;
}
vector
<int> prefixTable
;
initiate(prefixTable
, needle
);
buildPrefixTable(prefixTable
, needle
);
moveTable(prefixTable
);
int index
=search(haystack
, needle
, prefixTable
);
if (index
==-1)
{
return -1;
}else
{
return index
;
}
}
};
int main(int argc
, char const *argv
[])
{
return 0;
}
运行用时
结尾
看在我写了这么多注释的份上可以给我点个赞嘛,求求惹=]砰砰砰,给我加点写下去的油呀 @.@ 也欢迎关注我的账号呀=]
**开心code每一天**
