返回顶部

收藏

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. 2014-05-18 18:03:56快速排序 by 小项
  2. 2014-05-20 10:59:57利用先序,中序遍历恢复二叉树 by walker30
  3. 2014-05-21 15:34:33栈排序 by lucasli
  4. 2014-05-22 12:01:29二叉树前序和中序序列构造该二叉树 by niutao.linux
  5. 2014-06-12 15:10:10C++算法之回数 by qqmmcc
  6. 2014-07-09 13:45:46求 N 皇后问题回溯算法 by 小项
  7. 2014-07-13 12:07:01合并排序 by walker30
  8. 2014-07-23 19:43:01堆排序 by lucasli
  9. 2014-07-29 14:03:09大数四则运算 by 小项
  10. 2014-08-30 13:06:40数据构造有向图,邻接矩阵及拓扑序列 by 童学芬
  11. 2014-09-08 13:38:22线性表之不带头结点的单链表 by aiheng1988

发表评论