首页 > 试题广场 >

KMP算法

[编程题]KMP算法

热度指数：3583 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定两个字符串str和match，长度分别为N和M。实现一个算法，如果字符串str中含有子串match，则返回match在str中的开始位置，不含有则返回-1

若出现了多次，则按照升序输出所有出现位置

[要求]

时间复杂度为

输入描述:

第一行一个字符串str
第二行一个字符串match

输出描述:

输出若干个数，分别为match在str中出现的位置，从0开始标号。
若不存在输出-1

示例1

输入

acbc
bc

输出

示例2

输入

acbc
bcc

输出

-1

示例3

输入

ababab
ab

输出

0 2 4

备注:


保证字符集为小写字母

算法知识视频讲解

无心2019

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string str,match;
    getline(cin,str);
    getline(cin,match);
    bool f=false;
    for(int i=0;i<str.size()-match.size();i++)
    {
        string s=str.substr(i,match.size());
        if(s==match)
        {
            cout<<i<<" ";
            f=true;
        }
    }
    if(!f)
        cout<<-1;
    return 0;
}

发表于 2019-09-09 21:24:31 回复(1)

Java

pein531

既然题目说要用KMP算法，那就老老实实写个KMP算法来匹配就好了。而由于需要找到所有匹配的位置，因此要不断移动第一个字符串的起始指针来循环执行KMP算法来找到所有位置。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] str1 = br.readLine().toCharArray();
        char[] str2 = br.readLine().toCharArray();
        if(str1.length < str2.length){
            System.out.println(-1);
        }else{
            StringBuilder sb = new StringBuilder();
            int[] next = getNextArr(str2);
            int i1 = 0, i2 = 0;
            int find = kmp(str1, str2, i1, i2, next);
            while(find > -1){
                sb.append(find + " ");
                i1 = find + 1;      // i1不断后移，与str2匹配
                find = kmp(str1, str2, i1, i2, next);
            }
            System.out.println(sb.length() == 0? -1: sb.toString().trim());
        }
    }
    
    private static int kmp(char[] str1, char[] str2, int i1, int i2, int[] next) {
        if(i1 + str2.length >= str1.length) return -1;
        while(i1 < str1.length && i2 < str2.length){
            if(str1[i1] == str2[i2]){      // 字符相等，两个字符都移动
                i1 ++;
                i2 ++;
            }else if(next[i2] > -1){
                i2 = next[i2];     // 不相等且还能往前跳，则i2往前面跳
            }else{
                i1 ++;             // str2已经跳到0了还没法匹配成功，就只能移动str1的指针了
            }
        }
        return i2 == str2.length? i1 - i2: -1;
    }
    
    private static int[] getNextArr(char[] str) {
        if(str.length == 1) return new int[]{-1};
        int[] next = new int[str.length];
        next[0] = -1;
        int i = 2, prev = 0;
        while(i < str.length){
            if(str[i - 1] == str[prev]){
                next[i] = prev + 1;       // 最长与后缀相等的前缀长度+1
                prev ++;
                i ++;
            }else if(prev > 0){
                prev = next[prev];       // 不相等就往前跳
            }else{
                next[i] = prev;
                i ++;
            }
        }
        return next;
    }
}

发表于 2021-11-17 10:31:33 回复(1)

C++

麦芒2021

KMP算法

#include "bits/stdc++.h"

using namespace std;
int main()
{
    string T,P;
    cin>>T>>P;
    int len1=T.size();
    int len2=P.size();
    if(len1<len2){cout<<-1;return 0;}
    //求next数组
    vector<int> next(len2,0);
    next[0]=-1;
    int t=-1;
    int j=0;
    while(j<len2-1)
    {
        if(t<0||P[j]==P[t])
        {
            j++;t++;
            next[j]=P[j]!=P[t]?t:next[t];
        }
        else
        {
            t=next[t];
        }
    }
    int i=0;
    j=0;
    bool flag=0;
    while(i<len1&&j<len2)
    {
        if(j<0||T[i]==P[j]){i++;j++;}
        else {j=next[j];}
        //如果找到了一个匹配的，就右移一位继续寻找
        if(j==len2){flag=1;cout<<i-j<<" ";i=i-j+1;j=0;}
    }
    if(flag==0)cout<<-1;
    return 0;
}

发表于 2022-01-11 14:51:11 回复(0)

牛客887263087号

#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<int> next(string match){
if(match.size() == 1)
return {-1};
vector<int> nextArr(match.size());
nextArr[0] = -1;
nextArr[1] = 0;
int i = 2;
int cn = 0;
while(i < match.size()){
if(match[i - 1] == match[cn]){
nextArr[i++] = ++cn;
}
else if(cn > 0){
cn = nextArr[cn];
}
else{
match[i++] = 0;
}
}
return nextArr;
}

vector<int> getIndex(string str, string match){
int i1 = 0;
int i2 = 0;
vector<int> nextArr = next(match);
vector<int> ans;
while(i1 < str.size()){
if(str[i1] == match[i2]){
i1++;
i2++;
}
else if(i2 == 0){
i1++;
}
else{
i2 = nextArr[i2];
}
if(i2 == match.size()){
ans.push_back(i1 - i2);
i2 = 0;
}
}
if(ans.size() == 0)
ans.push_back(-1);
return ans;
}

int main(void){
string str, match;
cin >> str >> match;
vector<int> ans = getIndex(str, match);
for(auto a : ans)
cout << a << " ";
cout << endl;

}

字符串下标k位置

记录next信息,前面有多少个前缀 == 后缀

cn记录的不仅是前面信息，也代码那个位置的字符与i - 1进行比较。

发表于 2021-05-27 11:20:17 回复(0)

FrankKong

#include<iostream>
#include<vector>

using namespace std;

vector<int> getNext(string pattern){
    int k = -1; //匹配的前缀长度，-1代表长度为0
    vector<int> next(pattern.length(), -1);
    for(int i = 1; i < pattern.length(); i++){
        while(k > -1 && pattern[k + 1] != pattern[i]){
            k = next[k];
        }
        if(pattern[k + 1] == pattern[i]){
            k = k + 1;
        }
        next[i] = k;
    }
    return next;
}

vector<int> KMP(string str, string pattern){
    vector<int> next = getNext(pattern);
    int k = -1;
    vector<int> res;
    for(int i = 0; i < str.length(); i++){
        while(k > -1 && pattern[k + 1] != str[i]){
            k = next[k];
        }
        if(pattern[k + 1] == str[i]){
            k = k + 1;
        }
        if(k == pattern.length() - 1){
            res.push_back(i - pattern.length() + 1);
            k = -1;
        }
    }
    return res;
}

int main(){
    string str, pattern;
    cin >> str >> pattern;
    vector<int> res = KMP(str, pattern);
    if(res.empty()){
        cout << -1 << endl;
    }else{
        for(int i = 0; i < res.size(); i++){
            cout << res[i] << " ";
        }
    }
}

发表于 2020-10-13 13:53:49 回复(0)

楠楠呀

// 比较好的短的KMP
#include<iostream>
#include<string>
#include<vector>

using namespace std;

class Solution{
    public:
     vector<int> getpatternLen(string str,string match){
          //1.生成b数组
         //cout<<str<<endl;
         //cout<<match<<endl;
          vector<int> b(match.size() + 1);
          int j = -1;
          int i = 0;
          b[i] = j;
          while(i < match.size()){
              while(j>=0 && match[i] != match[j])
                   j = b[j];
              i++;
              j++;
              b[i] = j;
              
          }
          j = 0;//str
          i = 0;//pattern
          int index = 0;
          vector<int> res;
          while(j < str.size()){
              while(i>=0 && str[j] != match[i])
                  i = b[i];//跳转到该跳转的位置
              i++;
              j++;
              if(i == match.size()){
                  res.push_back(j - match.size());
                  if(j < str.size())
                      i = 0;
                  else
                      break;
              }
          }
          if(res.empty()){
              res.push_back(-1);
             
          }
              
          return res;
      }
};

int main(){
    string str;
    string match;
    getline(cin,str);
    getline(cin,match);
    vector<int> res;
    Solution c1;
    res = c1.getpatternLen(str,match);
    for(int i=0;i<res.size();i++){
        cout<<res[i]<<" ";
    }
    return 0;
    
}

发表于 2020-05-26 22:36:30 回复(0)

包子冲汤胡辣汤

#include<cstdio>
(802)#include<cstring>
int main(){
    char str[500010];
    char str1[500010];
    while(scanf("%s",str)!=EOF){
        scanf("%s",str1);
        int len1=strlen(str);
        int len2=strlen(str1);
        int flag=0;
        for(int i=0;i<=len1-len2;++i){
            int k=0;
            if(str[i]==str1[k]){
                int j=i;
                while(str[j]==str1[k]&&str[j]!='\0'){
                    j++;
                    k++;
                }
                if(k==len2){
                    if(flag==0)
                    {
                        printf("%d",i);
                        flag=1;
                    }else{
                        printf(" %d",i);
                    }
                }
            }
        }
        if(flag==0){
            printf("-1");
        }
    }
    return 0;
}

发表于 2020-03-25 18:56:46 回复(0)

Java

iuuu_p

#KMP算法
import java.util.*;
import java.io.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in); 
        String str = sc.nextLine();
        String match = sc.nextLine();
        KMP k = new KMP();
        List<Integer> result = k.kmp(str,match);
        //return result;
        for(int i : result){
            System.out.print(i);
            System.out.print(" ");
        }
    }
}
class KMP{
    public List<Integer> kmp(String str,String match){
        char[] matches = match.toCharArray();
        char[] strs = str.toCharArray();
        int[] next = getNext(matches);
        List<Integer> result = new ArrayList<>();
        int curmatch = 0;
        int index = 0;
        while(index<strs.length){
            while(curmatch != -1 && strs[index] != matches[curmatch]){
                curmatch = next[curmatch];
            }
            curmatch++;
            if(curmatch == matches.length){
                result.add(index-matches.length+1);
                curmatch = next[curmatch-1];
            }else
            	index++;
        }
        if(result.isEmpty())
            result.add(-1);
        return result;
    }
    private int[] getNext(char[] chars){
        int[] next = new int[chars.length];
        next[0] = -1;
        for(int i = 1;i<chars.length;i++){
            int k = i-1;
            while(k != 0 && chars[i-1] != chars[next[k]]){
                k = next[k];
            }
            next[i] = next[k]+1;
        }
        return next;
    }
}

发表于 2020-02-12 13:32:00 回复(0)

明月知何人

#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<int> getNext(const string& match) {
    vector<int> ret(match.length());
    ret[0] = -1;
    if(match.length() == 1)
        return ret;
    ret[1] = 0;
    int cn = ret[2-1];
    for(int i = 2; i < ret.size();) {
        if(match[i-1] == match[cn])
            ret[i++] = ++cn;
        else if(cn > 0)
            cn = ret[cn];
        else
            ret[i++] = 0;
    }
    return ret;
}

vector<int> KMP(const string& str, const string& match) {
    vector<int> ret;
    if(str.length() < match.length())
        return ret;
    
    vector<int> next = getNext(match);
    int i = 0;
    int j = 0;
    while(i < str.length()) {
        while(i < str.length() && j < match.length()) {
            if(str[i] == match[j]) {
                i++;
                j++;
            }
            else if(next[j] == -1) {
                    i++;
            }
            else {
                j = next[j];
            }
        }
        if(j == match.length()) {
            ret.push_back(i-j);
            i = i-j+1;  // 重点
            j = 0;
        }
    }
    return ret;
}

int main() {
    string str;
    cin >> str;
    string match;
    cin >> match;
    
    vector<int> ret = KMP(str, match);
    if(ret.empty())
        cout << -1 << endl;
    else {
        for(auto& e : ret)
            cout << e << " ";
        cout << endl;
    }
    
    return 0;
}

发表于 2020-01-18 16:44:01 回复(0)

C/C++

jdns1994

#include <iostream>
#include <vector>
#include <string>
using namespace std;

// 暴力匹配算法
int ViolentMatch(string s, string p) {
	int i = 0, j = 0, slen = s.size(), plen = p.size();
	while (i < slen && j < plen)
	{
		if (s[i] == p[j]){
			i++;
			j++;
		}
		else{
			i = i - j + 1;
			j = 0;
		}
	}
	
	if (j == plen) return i - j;
	else return -1;
}

// KMP算法
int KMP(string s, string p, vector<int>next) {
	int i = 0, j = 0, slen = s.size(), plen = p.size();
	while (i < slen && j < plen)
	{
		if (j == -1 || s[i] == p[j]){
			i++;
			j++;
		}
		else{
			j = next[j];
		}
	}

	if (j == plen) return i - j;
	else return -1;
}

// MultiKMP算法
vector<int> MultiKMP(string s, string p, vector<int>next) {
	vector<int> res;
	int i = 0, j = 0, slen = s.size(), plen = p.size();
	while (i < slen)
	{
		if (j == -1 || s[i] == p[j]){
			i++;
			j++;
		}
		else{
			j = next[j];
		}
		if (j == plen){
			res.push_back(i - j);
			j = 0;
		}
	}
	return res;
}

vector<int> GetNext(string p)
{
	vector<int> next(p.size());
	next[0] = -1;
	int k = -1, j = 0;
	while (j < p.size() - 1)
	{
		//p[k]表示前缀，p[j]表示后缀  
		if (k == -1 || p[j] == p[k]){
			++k;
			++j;
			if (p[j] != p[k]) next[j] = k;
			else next[j] = next[k];
		}
		else{
			k = next[k];
		}
	}
	return next;
}

int main(){
	string s1, s2;
	cin >> s1 >> s2;

	vector<int> next = GetNext(s2);

	// 暴力匹配第一次出现位置
	//cout << ViolentMatch(s1, s2) << endl;

	// KMP匹配第一次出现位置
	//cout << KMP(s1, s2, next) << endl;

	// KMP匹配无重复所有出现位置
	vector<int> res = MultiKMP(s1, s2, next);
	if (!res.empty()){
		for (int i = 0; i < res.size(); i++){
			cout << res[i] << ' ';
		}
		cout << endl;
	}
	else{
		cout << -1 << endl;
	}

	return 0;
}

编辑于 2019-11-20 11:19:30 回复(0)

提交观点

问题信息

字符串

上传者：小小

难度：

10条回答 29收藏 4187浏览

通过挑战的用户

查看代码

八武海

2023-03-07 20:46:27
龙月华

2023-03-02 13:12:37
空想之野

2023-02-27 22:18:23
我谢谢你哦

2023-02-24 23:34:30
爱读书的斑马很苦闷

2023-02-17 21:01:04

KMP算法

输入描述:

输出描述:

输入

输出

输入

输出

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题