KMP算法

　

kmp算法

于是，我的每个梦里都会有你

#include <iOStream>
#include <string>
using namespace std;

int* getNext(string s){
    if(s.size()<=1){
        return new int[1]{-1};
    }
    int len = s.size();
    int* next = new int[len];
    next[0] = -1;
    next[1] = 0;
    int current = 0;
    int i = 2;
    while(i < len){
        if(s[i-1] == s[current]){
            //如果前缀和后缀匹配
            next[i++] = ++current;
        }else{
            if(current > 0){
                //继续寻找current前面的最小字串
                current = next[current];
            }else{
                next[i++] = 0;
            }
        }
    }
    return next;
}

//s是主串，m是模式串
int getindexof(string s,string m){
    int* next = getNext(m);
    int i1,i2;
    i1 = i2 = 0;
    while(i1 < s.length() && i2 < m.length()){
        if(s[i1] == m[i2]){
            ++i1;
            ++i2;
        }
        //如果不等
        else
            {
                if(next[i2] == -1){
                //第一个字串就不相等
                ++i1;
            }else{
                //推动m到指定位置
                i2 = next[i2];
            }
        }
    }
    delete[] next;
    return i2 == m.length() ? i1-i2 : -1;
}


int main(int argc, char const *argv[])
{
    /* code */
    string s1,s2;
    getline(cin,s1);
    getline(cin,s2);
    int ans = getIndexOf(s1,s2);
    cout << ans << endl;
    return 0;
}

相关阅读

多元线性回归算法学习笔记

多元线性回归的思路 和简单线性回归相比 x 由一个特征，变为一个向量 X，含有多个特征。 找出一条直线（多维度实际不是直线，只是为了

排列组合算法

题目：求（1）一组数字的全排列（2）一组数字中某几个数字的组合一、排列算法：全排列是将一组数按一定顺序进行排列，如果这组数有n个，那么全排

【华为2018年校园招聘】算法岗笔试题

我的个人微信公众号：Microstrong 微信公众号ID：MicrostrongAI 公众号介绍：Microstrong(小强)同学主要研究机器学习、深度学习、计算

排序算法：冒泡排序

冒泡排序是一种交换排序。 什么是交换排序呢？ 交换排序：两两比较待排序的关键字，并交换不满足次序要求的那对数，直到整个表都满足次序

BP神经网络的Matlab实现——人工智能算法

这几天在各大媒体上接触到了人工智能机器学习，觉得很有意思，于是开始入门最简单的机器算法——神经网络训练算法（Neural Network Tra