KMP

#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;

void GetNext(char *str,int next[])
{
    int j,k;
    j=0;k=-1;next[0]=-1;
    while(str[j]!='\0')
    {
        if(k==-1 || str[j]==str[k])
        {
            j++;k++;
            next[j]=k;
        }
        else k=next[k];
    }
}

int KMPIndex(char *s,char *t)
{
    int lent=strlen(t);
    int next[100],i=0,j=0,v;
    GetNext(t,next);
    while(s[i]!='\0' && t[j]!='\0')
    {
        if(j==-1 || s[i]==t[j])
        {
            i++;j++;
        }
        else j=next[j];
    }
    if(j>=lent) v=i-lent;
    else v=-1;
    return v;
}

int main()
{
    char s[]="ababcabsds";
    char t[]="abcd";
    cout<<KMPIndex(s,t);
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • poj 2251 Dungeon Master(广搜)

    题意:三维空间,可以走上下左右前后六个方向,求最短路径,BFS #include<stdio.h> #include<queue> #include<strin...

    用户1624346
  • Insertion Sort List

    家里网实在太烂了,弄得我都不想上网,每次打开oj特别慢,提交题目等刷出来更慢。对于这题感觉脑子不好用啊,写的好繁琐。不过所幸最终脑子还是转过乐弯。。。就是指针n...

    用户1624346
  • poj 1426 Find The Multiple (广搜)

    http://poj.org/problem?id=1426 题意:求n的倍数m,对于m的要是求所有位的数必须是0或1  a nonzero multiple ...

    用户1624346
  • KMP算法

    KMP为的是解决2字符串匹配问题的算法,检查一个字符串是否为另一个的子串,sub = "abc" , str = "aabcd" ,str里包含了一个sub,K...

    xiangzhihong
  • 来我们再聊聊 KMP 算法 -- 我懂,你也得懂

    搞了一整天的KMP,自己动手写,先是感觉自己搞懂了,写完提交又崩溃了。反反复复一整天,刚刚总算是半抄半写过去了。

    看、未来
  • 单链表反转的分析及实现

    我先画一个单链表,这个单链表有4个元素。我的思路就是,每次把第二个元素提到最前面来。比如下面是第一次交换,我们先让头结点的next域指向结点a2,再让结点a1...

    猿人谷
  • LinkedList - 92. Reverse Linked List II

    Reverse a linked list from position m to n. Do it in one-pass.

    用户5705150
  • 吃透洋葱模型

    作者:掘金@苏里 https://juejin.im/post/6844904025767280648

    zz_jesse
  • leetcode:83 删除排序链表中的重复元素

    问题? 如果next没有值的话,会报错的。 因为要相等啊,比较啊,有值才能比较是吧。 那为什么p.next=p.next.next;如果p.next.ne...

    用户7873631
  • (原创)详解KMP算法

    KMP算法应该是每一本《数据结构》书都会讲的,算是知名度最高的算法之一了,但很可惜,我大二那年压根就没看懂过~~~ 之后也在很多地方也都经常看到讲解KMP算法的...

    marsggbo

扫码关注云+社区

领取腾讯云代金券