kmp算法

kmp优化版1

/*
 * @Author: Mr.Sen
 * @LastEditTime: 2020-04-07 23:56:34
 * @Website1: 449293786.site
 * @Website2: sluowanx.cn
 */
#include<bits/stdc++.h>
using namespace std;
int* get_next(string pattern)
{
    //get next array and return a point
    int size=pattern.length();
    int* next=new int[size];
    //动态申请一块空间
    next[0]=-1;
    //给零号位初始化为-1，当零号位不能匹配时整体后移一位
    int j=0,k=-1;
    while (j<pattern.length()-1)
    {
        if (k==-1||pattern[j]==pattern[k])
        {
            if (pattern[++j]==pattern[++k])
            {
                next[j]=next[k];
            }
            else next[j]=k;
        }
        else k=next[k];
    }
    return next;
}

int KMP(string haystack, string needle)
{ 
    if(needle == "") 
        return 0; 
    int* next = get_next(needle);
    int i=0;
    int j=0; 
    while(i < int(haystack.length()) && (j < int(needle.length())))
    { 
        if(j == -1 || haystack[i] == needle[j])
        {
            i++;j++; 
        }
        else
        {
            j = next[j];
        }
    }
    if(j == needle.length())
    {
        return i-j; 
    }
    else
    {
        return -1; 
    }
}

int main()
{
    string cmp,pattern;
    cin>>cmp>>pattern;
    cout<<KMP(cmp,pattern);
    return 0;
}

kmp原版

#include <bits/stdc++.h>
using namespace std;
int* get_next(string needle)
{
    int* next = new int[needle.length()];
    next[0] = -1;
    int j = 0;
    int k = -1;
    int size = needle.length();
    while(j<size - 1)
    {
        if(k == -1 || needle[k] == needle[j])
        {
            j++;k++; next[j] = k;
        }
        else
        {
            k = next[k];
        }
    }
    return next;
}
int KMP(string haystack, string needle)
{
    if(needle == "") return 0;
    int* next = get_next(needle);
    int i=0;
    int j=0;
    while(i < int(haystack.length()) && (j < int(needle.length())))
    {
        if(j == -1 || haystack[i] == needle[j])
        {
            i++;j++;
        }
        else
        {
            j = next[j];
        }
    }
    if(j == needle.length())
    {
        return i-j;
    }
    else
    {
        return -1;
    }
} 
int main()
{
    string haystuck,pattern;
    cin>>haystuck>>pattern;
    int location=KMP(haystuck,pattern);
    cout<<location<<endl;
    return 0;
}

kmp确定有限状态机版

/*
 * @Author: Mr.Sen
 * @LastEditTime: 2020-04-08 13:08:01
 * @Website1: 449293786.site
 * @Website2: sluowanx.cn
 */
#include<bits/stdc++.h>
using namespace std;
int next1[100][256];
void get_next(string pattern)
{
    int shadow=0;
    int size=pattern.length();
    next1[0][pattern[0]]=1;
    for (int i=1;i<size;i++)
    {
        for (int j=0;j<256;j++)
        {
            next1[i][j]=next1[shadow][j];
        }
        next1[i][pattern[i]]=i+1;
        shadow=next1[shadow][pattern[i]];
    }
}
int search(string cmp,string pattern)
{
    int size_pattern=pattern.length();
    int size_cmp=cmp.length();
    int j=0;
    for (int i=0;i<cmp.length();i++)
    {
        j=next1[j][cmp[i]];
        if (j==size_pattern)
            return i-size_pattern+1;
    }
    return -1;
}
int main()
{
    get_next("sip");
    cout<<search("missisasipi","sip");
    return 0;
}