顺序串的实现(插入、截取、匹配)

87 阅读 0 评论 58 点赞

我是靠谱客的博主美丽钢铁侠，最近开发中收集的这篇文章主要介绍顺序串的实现(插入、截取、匹配)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

实验内容：

1. 设计可以在主串s中第i个位置之前插入一个子串t的程序。

2. 设计可以在主串s中从第i个位置开始共取m个字符，求子串的程序。

3. 设计一个程序求子串t在主串s中的起始位置

匹配算法中实现了bf算法和 kmp 两种算法

Code：

#include <stdio.h>
#define Maxsize 100

int next[Maxsize];
typedef struct
{
    char data[Maxsize];
    int length;
}SqString;

//初始化串
void init_string(SqString &s,char *s1)
{
    int i;
    for(i=0;s1[i]!='';i++)
        s.data[i]=s1[i];
    s.length=i;
}

//输出串
void DispStr(SqString s)
{
    int i;
    if(s.length>0)
    {
        for(i=0;i<s.length;i++)
            printf("%c",s.data[i]);
        printf("n");
    }
}

//插入
SqString insert_string(SqString s,SqString t,int p)
{
    int i;
    SqString str;
    for(i=0;i<p-1;i++)
        str.data[i]=s.data[i];
    for(i=0;i<t.length;i++)
        str.data[i+p-1]=t.data[i];
    for(i=p-1;i<s.length;i++)
        str.data[t.length+i]=s.data[i];
    str.length=s.length+t.length;
    return str;
}


//取子串
SqString Takeout_string(SqString s,int i,int j)
{
    SqString str;
    int k;
    for(k=0;k<j;k++)
    {
        str.data[k]=s.data[i+k-1];
    }
    str.length=j;
    return str;
}


//bf匹配
int find_string(SqString s,SqString t)
{
    int i,j,flage;
    for(i=0;i<s.length;i++)
    {
        for(j=0;i<t.length;j++)
        {
            if(s.data[i+j]!=t.data[j])
            {
                break;
            }
              if(j==t.length-1)
                return i+1;
        }
    }
        return -1;
}


//kmp匹配
void  getnext(SqString t,int next[])
{
    int tlen=t.length;
    next[0]=-1;
    int k=-1;
    int j=0;
    while(j<tlen-1)
    {
        //t[k]表示前缀,t[j]表示后缀
        if(k==-1||t.data[j]==t.data[k])
        {
            k++;
            j++;
            next[j]=k;
        }
        else
        {
            k=next[k];
        }
    }
}

int kmpsearch(SqString s,SqString t)
{
    int i=0,j=0;
    int slen=s.length,tlen=t.length;
    while(i<slen&&j<tlen)
    {
        //如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++
        if(j==-1||s.data[i]==t.data[j])
        {
            i++;
            j++;
        }
        else
        {
            //如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]
            //next[j]即为j所对应的next值  ,相当于模式串t相对于文本串s向右移动了j - next [j] 位。
            j=next[j];
        }
    }
    if(j==tlen)
        return i-j+1;
    else
        return -1;
}

int main()
{
        //raw为主串,tem为模板串,res为操作后的串
        SqString raw,tem,res;
        int p;                          //插入的位置
        char s1[Maxsize],s2[Maxsize];
        printf("请输入主串rawn");
        scanf("%s",s1);
        init_string(raw,s1);
        printf("请输入模板串temn");
        scanf("%s",s2);
        init_string(tem,s2);

        printf("请输入要插入的位置n");
        scanf("%d",&p);
        if(p<=0||p>raw.length)
            printf("插入位置有误!n");
        else
        {
            res=insert_string(raw,tem,p);
            printf("插入后的主串为："); DispStr(res);
        }

        int start,length;
        printf("请输入截取的位置start和截取的长度lengthn");
        scanf("%d%d",&start,&length);
        if(start<=0||length+start>raw.length||start>raw.length)
        {
            printf("输入截取字串的位置有误!n");
        }
        else
        {
            res=Takeout_string(raw,start,length);
            printf("截取后的子串为："); DispStr(res);
        }

        int ans;

        /*bf匹配
        ans=find_string(raw,tem);
        if(ans==-1)
           printf("查找失败,没有在主串中找到模板串n");
        else
           printf("模板串在主串中的位置为%dn",ans);
        */
        //kmp匹配
        getnext(tem,next);
        ans=kmpsearch(raw,tem);
        if(ans==-1)
          printf("查找失败,没有在主串中找到模板串n");
        else
           printf("模板串在主串中的位置为%dn",ans);


    return 0;
}