实现函数 strStr。
函数声明如下：
char *strStr(char *str, char *dest)
返回一个指针，指向dest第一次在str中出现的位置，如果dest不是str的子串，则返回null
[编程题]实现strstr函数
//KMP算法
public class Solution {
public int[] getNext(String needle ){
int j=-1;
int i=0;
int[] next = new int[needle.length()];
next[i]=j;
while(i<needle.length()-1){
if (j==-1||needle.charAt(i)==needle.charAt(j)){
i++;
j++;
if(needle.charAt(i)!=needle.charAt(j)){
next[i]=j;
}else{
next[i]=next[j];
}
}else{
j=next[j];
}
}
return next;
}
public String strStr(String haystack, String needle) {
if(haystack==null||needle==null||needle.length()==0){
return haystack;
}
if(needle.length()>haystack.length()){
return null;
}
int[] next = getNext(needle);
int i=0;
int j=0;
while(i<haystack.length()&&j<needle.length()){
if(j==-1||haystack.charAt(i)==needle.charAt(j)){
i++;
j++;
}else{
j=next[j];
}
}
if(j>=needle.length()){
return haystack.substring(i-needle.length());
}else{
return null;
}
}
}
发表于 2016-10-30 21:43:55
回复(0)
public class Solution {
public String strStr(String haystack, String needle) {
if(haystack==null || needle == null || needle.length()==0)
return haystack;
if(needle.length()>haystack.length())
return null;
char[] a = haystack.toCharArray();
char[] b = needle.toCharArray();
int[] next = getNextArray(b);
int i = 0,j = 0;
while (i < a.length) {
while (j >= 0 && a[i] != b[j]) {
j = next[j];
}
i++;
j++;
if (j == b.length) {
return haystack.substring(i - b.length);
}
}
return null;
}
private int[] getNextArray(char[] s){
if(s.length==1)
return new int[]{-1};
int[] next = new int[s.length];
next[0] = -1;
next[1] = 0;
int pos = 2;
int cn = 0;
while(pos<next.length){
if(s[pos-1]==s[cn])
next[pos++] = ++cn;
else if(cn>0)
cn = next[cn];
else
next[pos++] = 0;
}
return next;
}
}
发表于 2016-06-04 12:33:12
回复(0)
使用指针去记录位置
char *strStr(char *haystack, char *needle) {
if (*needle == '\0') return haystack; // 若needle为空,返回haystack
if (*haystack == '\0') return NULL; // 否则,若haystack为空,则返回NULL
while (*haystack != '\0') { // 从haystack的每一个位置开始查找,是否有和needle相同的字符串
char *p = haystack, *q = needle;
while (*p != '\0' && *q != '\0' && *p == *q) {p ++; q ++;} // 逐个比对是否相同
if (*q == '\0') return haystack; // 若有,则直接返回当前haystack的位置
haystack ++; // 否则继续后移
}
return NULL;
}
发表于 2019-06-20 20:17:02
回复(0)
public class Solution {
public String strStr(String haystack, String needle) {
if (haystack == null || needle == null || haystack.length() < needle.length())
return null;
if (needle.length() == 0)
return haystack.substring(0);
for (int i = 0; i <= haystack.length() - needle.length(); i++) {
for (int j = 0; j < needle.length(); j++) {
if (haystack.substring(i, i + needle.length()).equals(needle))
return haystack.substring(i);
}
}
return null;
}
}
编辑于 2017-07-19 11:39:46
回复(3)
class Solution {
public:
char *strStr(char *haystack, char *needle) {
int m = strlen(haystack);
int n = strlen(needle);
if(m < n)
return NULL;
int d = m - n;
for(int i=0;i<=d;i++)
{
int j = 0;
for(;j<n;j++)
{
if(haystack[i+j] != needle[j])
break; } if(j == n) return haystack + i; } return NULL;
}
};
发表于 2017-09-24 02:25:32
回复(0)
//Sunday算法
char *strStr(char *haystack, char *needle) {
int len1=strlen(haystack),len2=strlen(needle);
if(len2==0) return haystack;
if(len2>len1) return NULL;
//用map保存needle中每个字符从后往前第一次出现的位置
unordered_map<char,int> pos;
for(int i=len2-1;i>=0;--i){
if(pos.find(needle[i])==pos.end())
pos[needle[i]]=i;
}
int i=0,j=0;
while(i<len1&&j<len2){
if(haystack[i]==needle[j]){
++i;
++j;
}else{
int index=pos[haystack[i+len2-j]];
i=i+len2-j-index;
j=0;
}
if(j==len2)
return &haystack[i-len2];
}
return NULL;
}
编辑于 2017-05-12 11:23:46
回复(0)
public class Solution {
public static String strStr(String haystack, String needle) {
if(haystack == null || needle == null || needle.length() == 0) return haystack;
if(needle.length() > haystack.length()) return null;
for (int i = 0; i < haystack.length(); i ++ ) {
if(haystack.charAt(i) == needle.charAt(0) && i + needle.length() <= haystack.length() && haystack.substring(i, i + needle.length()).equals(needle)) {
return haystack.substring(i);
}
}
return null;
}
}
发表于 2016-11-04 22:17:16
回复(0)
public class Solution {
public String strStr(String haystack, String needle) {
int lengthOfStack = haystack.length();
int lengthOfNeedle = needle.length();
if(haystack == null || needle == null ||lengthOfStack < lengthOfNeedle ){
return null;
}
for(int i=0; i<=(lengthOfStack - lengthOfNeedle);i++){
if(haystack.substring(i, i+lengthOfNeedle).equals(needle)){
return haystack.substring(i);
}
}
return null;
}
}
发表于 2016-07-12 20:04:39
回复(0)
KMP算法
有一个问题，把求next数组的函数返回值改成引用就超时是咋回事
class Solution {
public:
vector<int> getNext(char* ms){
int l=strlen(ms);
vector<int> next(l);
if(l==1){
next[0]=-1;
return next;
}
next[0]=-1;
next[1]=0;
int pos=2;
int cn=0;
while(pos<next.size()){
if(ms[pos-1]==ms[cn])
next[pos++]=++cn;
else if(cn>0)
cn=next[cn];
else
next[pos++]=0;
}
return next;
}
char *strStr(char *haystack, char *needle) {
int l1=strlen(haystack),l2=strlen(needle);
if(l1<l2)
return NULL;
if(l1==0||l2==0)
return haystack;
int si=0,mi=0;
vector<int> next=getNext(needle);
while(si<l1&&mi<l2){
if(haystack[si]==needle[mi]){
si++;
mi++;
}else if(next[mi]==-1){
si++;
}else{
mi=next[mi];
}
}
return mi==l2 ? &haystack[si-mi] : NULL;
}
};
编辑于 2017-03-04 17:58:32
回复(2)
// 这样看起来简单理解一点？
char *strStr(char *haystack, char *needle)
{
int m = strlen(haystack),n = strlen(needle);
if(m<n) return nullptr;
int diff = m-n+1;
for(int start=0;start<diff;start++)
{
int j=0;
for(;j<n;j++)
{
if(haystack[start+j] != needle[j])
break;
}
if(j==n)
{
return haystack+start;
}
}
return nullptr;
}
发表于 2017-07-12 19:51:30
回复(0)
竟然过了
class Solution {
public:
char *strStr(char *str, char *dest) {
const char* r1 = str;
const char* r2 = dest;
while (*r2!='\0'&&*r1!='\0') {
if (*r1 == *r2) {
r1++, r2++;}
else {
r1 =++str;
r2 = dest; }
}
if (*r2 == 0)
return str;
else
return NULL;
}
};
发表于 2022-09-23 14:35:43
回复(0)
public class Solution {
public String strStr(String str, String dest) {
char[] t = str.toCharArray();
char[] p = dest.toCharArray();
if (p.length == 0) {
return str;
}
int i = 0, j = 0;
int[] next = getNext(dest);
while (i < t.length && j < p.length) {
if (j == -1 || t[i] == p[j]) {
i++;
j++;
} else {
j = next[j];
}
}
if (j == p.length) {
return str.substring(i - j);
}
return null;
}
public static int[] getNext(String ps) {
char[] p = ps.toCharArray();
int[] next = new int[p.length];
int j = 0;
int k = -1;
next[0] = -1;
while (j < p.length - 1) {
if (k == -1 || p[k] == p[j]) {
if (p[++k] == p[++j]) {
next[j] = next[k];
} else {
next[j] = k;
}
} else {
k = next[k];
}
}
return next;
}
}
发表于 2021-10-02 10:03:16
回复(0)
KMP算法，关键在于求next数组，求next数组搞了好久都没搞懂，干脆记住算了。。。吧
//
// Created by jt on 2020/8/14.
//
#include <string>
using namespace std;
class Solution {
public:
char *strStr(char *haystack, char *needle) {
int size1 = strlen(haystack), size2 = strlen(needle);
if (size2 == 0) return haystack;
int next[size2], i = 0, j = 0;
getNext(needle, next, size2);
while(i < size1 && j < size2) {
if (j == -1 || haystack[i] == needle[j]) {
++i;
++j;
} else {
j = next[j];
}
}
if (j == size2) return haystack + i - j;
else return nullptr;
}
void getNext(char *a, int *next, int size) {
int i = 0, j = -1; // i指向尾子串尾部，j指向头子串尾部
next[0] = -1;
while (i < size) {
if (j == -1 || a[i] == a[j]) {
if (a[++i] == a[++j]) next[i] = next[j];
else next[i] = j;
} else j = next[j];
}
}
};
发表于 2020-08-15 12:55:40
回复(0)
哪个老哥能解释一下：
先判断needle就正确，先判断 haystack就错误，是怎么回事呢？
char *strStr(char *haystack, char *needle) {
char* res = nullptr;
//正确的：
if(*needle =='\0')
return haystack;
if(*haystack == '\0')
return nullptr;
//错误的：
if(*haystack == '\0')
return nullptr;
if(*needle =='\0')
return haystack；
}
//为什么？？？
发表于 2020-07-07 19:24:03
回复(3)
KMP算法，求出nextval，设子串长度为m，主串长度为n，但m>>n时，时间复杂度为近似O(m)
class Solution {
public:
void inital(int* &findnext,char *needle,int n){
findnext[0]=-1;
for(int i=1;i<n;i++){/*第i个位子匹配不成功*/
int off = 1; //措off个位子匹配
while(off<=i){
if(needle[i]==needle[i-off])
off++;
else{
int j;
for(j=0;j<i-off;j++){
if(needle[j]!=needle[j+off]){
off++;
break;
}
}
if(j==i-off){
findnext[i]=i-off;
break;
}
}
}
if(off==i+1)
findnext[i]=-1;
}
}
char *strStr(char *haystack, char *needle) {
int sublen = 0;
int len=0;
int i=0;
while(needle[i]!='\0'){
sublen++;
i++;
}
i=0;
while(haystack[i]!=0){
len++;
i++;
}
if(sublen==0 && len==0)
return haystack;
if(sublen!=0&&len==0)
return NULL;
if(sublen==0 && len!=0)
return haystack;
int *findnext=new int[sublen];
inital(findnext,needle,sublen);
int j=0;
i=0;
while(haystack[j]!='\0'){
if(haystack[j]==needle[i]){
if(i==sublen-1){
return haystack+j-sublen+1;
}
j++;
i++;
}else{
i=findnext[i];
if(i==-1){
i=0;
j++;
}
}
}
return NULL;
}
};
发表于 2020-05-01 10:57:36
回复(0)
public class Solution {
/**
* leetcode: implement-strstr
* 虽然读不懂题目,但是看了讨论是要求包含needle子串的起点,返回haystack从这个起点开始的所有字符串
* 例如 haystack = "abcdefg", needle = "cd", 返回cdefg
* 1.首先想到的是最简单的做法,遍历haystack,每走一位就匹配一次needle,看是否全部包含
* 这种方法最坏情况下时间复杂度O((n-m+1)*m),平均时间复杂度O(n+m) ps:我自己不会算,参考https://blog.csdn.net/ylyg050518/article/details/78825387
* 2.kmp算法.
* 具体思想就是根据匹配串needle求一个next数组,表示如果当前字母不匹配,跳转到哪里开始匹配,而不是每次都从头开始匹配
* 例如haystack = "abcdababef", needle = "ababe", 假设i是needle的指针,当i=4(needle.charAt(i) == 'e')不匹配时,应该把i置为2而不是0
* 当i=4时才匹配失败,说明'abab'一定匹配通过,因此下次没必要从头开始匹配,而可以从i=2开始匹配,因为'abab'相同的最长前缀后缀为'ab'.
* 这里可能有点难理解,因为这就是kmp的核心,'abab'的所有前缀为[a, ab, aba], 所有后缀为[b, ab, bab],所以相同的最长前缀后缀为'ab'
* 因此当'e'匹配失败时,表示后缀ab一定能够匹配通过,所以前缀ab也一定能匹配通过,这时就不需要再回溯回去再匹配一次前缀,直接从前缀ab后面开始匹配就行
* 具体的实现可以网上搜索,https://www.cnblogs.com/ZuoAndFutureGirl/p/9028287.html 这篇文章讲的很不错而且有图说明
*/
public String strStr(String haystack, String needle) {
if (needle.length() == 0) return haystack;
int[] next = next(needle);
int a = 0, b = 0;
while (a < haystack.length()) {
if (haystack.charAt(a) == needle.charAt(b)) {
a ++;
b ++;
} else {
if (next[b] >= 0) {
b = next[b];
} else {
a ++;
b = 0;
}
}
if (b == needle.length()) {
break;
}
}
if (b == needle.length()) {
return haystack.substring(a - b);
}
return null;
}
/**
* 动态规划求出next数组
*/
private static int[] next(String p) {
int[] r = new int[p.length()];
// 求出到每个字符的最长相同前缀后缀的长度
for (int i = 1 ; i < p.length() ; i ++) {
if (r[i - 1] == 0) {
r[i] = p.charAt(i) == p.charAt(0) ? 1 : 0;
} else {
if (p.charAt(i) == p.charAt(r[i - 1])) {
r[i] = r[i - 1] + 1;
} else {
r[i] = p.charAt(i) == p.charAt(0) ? 1 : 0;
}
}
}
// 整体右移,因为next数组表示的是当这个字符匹配失败该跳到哪里去,确切来说,当前字符只关心前一个字符的最长相同前缀后缀的长度
for (int i = r.length - 1 ; i > 0 ; i --) {
r[i] = r[i - 1];
}
r[0] = -1;
return r;
}
}
发表于 2019-08-02 15:24:08
回复(0)
class Solution {
public:
char *strStr(char *haystack, char *needle) {
int heyLen = strlen(haystack);
int needLen = strlen(needle);
if (heyLen<needLen)
return NULL;
string hh;
string nn;
while (*haystack != '\0') {
hh += *haystack;
haystack++;
}
while (*needle != '\0') {
nn += *needle;
needle++;
}
haystack = haystack - heyLen;
for (int i = 0;i <= heyLen-needLen;i++) {
if (hh.substr(i, needLen) == nn)
return (haystack+i);
}
return NULL;
}
};
public:
char *strStr(char *haystack, char *needle) {
int heyLen = strlen(haystack);
int needLen = strlen(needle);
if (heyLen<needLen)
return NULL;
string hh;
string nn;
while (*haystack != '\0') {
hh += *haystack;
haystack++;
}
while (*needle != '\0') {
nn += *needle;
needle++;
}
haystack = haystack - heyLen;
for (int i = 0;i <= heyLen-needLen;i++) {
if (hh.substr(i, needLen) == nn)
return (haystack+i);
}
return NULL;
}
};
发表于 2019-08-02 10:40:08
回复(0)
问题信息
难度：
57条回答
57收藏
22008浏览
通过挑战的用户
查看代码-
2023-03-03 17:34:05
-
2022-11-26 10:29:35 -
2022-10-08 20:51:42
-
2022-09-23 14:34:10
-
2022-09-13 11:47:05
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
