返回顶部

收藏

KMP算法实现字符串搜索

更多
#include<stdio.h>
#define maxsize 100
typedef struct string
{
    int  n;
    char s[maxsize];
}string;
int get_nextval(string &T,int nextval[])
{
    int i=1;
    int j=0;
    nextval[1]=0;
    while(i<T.n)
    {
        if(j==0||T.s[i]==T.s[j])
        {
            ++i;
            ++j;
            nextval[i]=j;
        }
        else
            j=nextval[j];
    }
    return 0;
}
int Index(string &S,string &T,int pos)
{
    int i=pos;
    int j=1;
    int nextval[255];
    get_nextval(T,nextval);
    while(i<=S.n&&j<=T.n)
    {
        if(j==0||S.s[i]==T.s[j])
        {
            ++i;
            ++j;
        }
        else
            j=nextval[j];
    }
    if(j>T.n)
        return i-T.n;
    else
        return 0;
}
int main()
{
    string S,T;
    char c;
    int i=1,m;
    printf("请输入原字符串S,以#号结尾");
    while((c=getchar())!='#')
    {
        S.s[i]=c;
        i++;
    }
    S.n=i-1;
    printf("请输入检测字符串T,以#号结尾");
    fflush(stdin);
    i=1;
    while((c=getchar())!='#')
    {
        T.s[i]=c;
        i++;
    }
    T.n=i-1;
    m=Index(S,T,1);
    printf("检测结果为:");
    if(m==0)
        printf("找不到字符串!");
    else
        printf("找到字符串,从S的第%d个位置开始\\n",m);
    return 0;
}
//该片段来自于http://outofmemory.cn

标签:c++,算法

收藏

0人收藏

支持

0

反对

0

»更多 您可能感兴趣的代码
  1. 2013-07-17 19:11:32c++动态规划算法计算网络的最长路线和最短路线 by lucasli
  2. 2014-02-12 11:56:53C++算法之数星星 by lucasli
  3. 2014-02-21 12:23:12C++实例解析哈夫曼树 by lucasli
  4. 2014-03-30 15:29:42C++算法之链表排序 by 跳跳虎
  5. 2014-04-24 17:42:39C++算法之链表重合 by lucasli
  6. 2014-05-20 10:42:08双向循环列表 by Kevin.
  7. 2014-05-27 14:13:38网络中两点最短路径 Dijkstra 算法 by 千万不要郁闷
  8. 2014-06-08 10:40:28数字的全排列 by sxgkwei
  9. 2014-06-24 14:17:58C++ 算法之单词统计 by 小项
  10. 2014-07-06 21:23:00死锁检测算法 by 童学芬
  11. 2014-07-20 12:34:50傻瓜递归 by 童学芬
相关聚客文章
  1. abyssss 发表 2014-05-20 03:23:39 数据结构 最小堆 数组实现
  2. dianlujitao 发表 2014-10-17 13:56:48 POJ 1611 The Suspects
  3. surgesoft 发表 2014-10-28 08:01:58 LeetCode OJ: Restore IP Addresses
  4. espace 发表 2015-07-18 17:43:14 Two Sum
  5. bystander 发表 2013-05-15 10:37:24 倒水问题求解(C++)
  6. dianlujitao 发表 2014-10-17 14:11:26 POJ 1328 Radar Installation
  7. bystander 发表 2013-04-01 10:12:37 [藏]关于B树的一篇文章
  8. lvfuyu 发表 2015-04-12 08:53:30 [hihocoder]矩阵快速幂
  9. lvfuyu 发表 2015-04-18 09:13:32 [hihocoder]二分查找
  10. leaver 发表 2013-05-27 02:55:49 求整数1-N范围和为N的所有组合
  11. cijianzy 发表 2015-05-01 14:20:33 修复了中文维基百科基数排序C++代码的一个bug
  12. dianlujitao 发表 2013-11-04 11:49:12 【NOIP2012提高组】Vigenère密码 模拟 打表

发表评论