| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 661 人关注过本帖
标题:kmp字符串匹配代码问题
只看楼主 加入收藏
ycc892009
Rank: 2
等 级:论坛游民
帖 子:34
专家分:90
注 册:2009-12-23
收藏
 问题点数:0 回复次数:1 
kmp字符串匹配代码问题
程序代码:
#include <iostream>
#include <string.h>
using namespace std;

//kmp算法的next函数下标从0开始
void next(const char *szMsg, int next1[])
{
   
    int j = 0;
    int k = -1;
     next1[0] = -1;
    while(j<strlen(szMsg)-1)//次数,以下的需要画图理解
    {
        if (k == -1||szMsg[j] == szMsg[k])//字符匹配
        {
            ++j;
            ++k;
            if (szMsg[j] != szMsg[k]) //
                next1[j] = k;//
            else//相等就是说有重复的字符
            next1[j] = next1[k];
        }
        else
        {
            k = next1[k];//k返回到next(k)
        }
    }

return;
}

int Index(const char *szMsg, const char* str)
{
    int lenszMsg=strlen(szMsg);
    int len = strlen(str);
    int *next1 = new int[len];
    next(szMsg, next1);//next函数
    int i = 0;
    int j = 0;
    while(i < lenszMsg&& j<len)
    {
        if (j ==-1||szMsg[i] == str[j])//字符匹配
        {
            i++;//往下匹配
            j++;
        }
        else
            j = next1[j];//不匹配往回找,i不变
    }

    if (j==len)
        return i-len;//匹配返回从第几个下标开始匹配
    return -1;//不匹配
}

int main()
{
    char szMsg[256];
    char str[256];
    cout << "输入目标串:" ;
    cin >> szMsg;
    cout << "输入子串:";
    cin >> str;
    int len =strlen(szMsg);
   
    if (Index(szMsg,str)!=-1)
        cout << "" << szMsg << " 中可以找到 " << str <<endl;
    else
        cout << "" << szMsg << " 中找不到 " << str <<endl;

return 0;
}
图片附件: 游客没有浏览图片的权限,请 登录注册

输入的字符串小一点有没有错误。我调不出来原因
搜索更多相关主题的帖子: kmp 字符 代码 
2010-11-17 18:42
ycc892009
Rank: 2
等 级:论坛游民
帖 子:34
专家分:90
注 册:2009-12-23
收藏
得分:0 
程序代码:
int lenszMsg=strlen(szMsg);
    int len = strlen(str);
    int *next1 = new int[len];
    next(szMsg, next1);//next函数
原因已经找到
数组越界问题
应该改为
程序代码:
int lenszMsg=strlen(szMsg);
    int len = strlen(str);
    int *next1 = new int[len];
    next(str, next1);//next函数



到达理想的界面是我的目标,成功却不是快捷方式!
2010-11-17 19:19
快速回复:kmp字符串匹配代码问题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.029836 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved