串

1）串的基本操作

#include <stdio.h>
#define MaxSize 255
typedef struct 
{
    char ch[MaxSize];
    int len;
}MyString;
//从指定位序开始截取串的子串
bool SubString(MyString &Sub,MyString S,int pos,int len)
{
    if(pos+len-1>S.len) return false; //子串范围越界
    for(int i=pos;i<pos+len;i++)
    {
        Sub.ch[i-pos+1]=S.ch[i];
    }
    Sub.len=len;
    return true;
}
//比较两个串的大小
int CompareString(MyString S1,MyString S2)
{
    //逐个字符比较
    for(int i=1;i<=S1.len&&i<=S2.len;i++)
    {
        if(S1.ch[i]!=S2.ch[i]) return S1.ch[i]-S2.ch[i];    
    }
    //扫描过的字符皆相同，比较两字符串长度
    return S1.len-S2.len;
}
//定位子串
int indexString(MyString S,MyString Sub)
{
    //暂存截取串
    int i=1;
    MyString temp;
    temp.len=Sub.len;
    while(i<=S.len-Sub.len+1)
    {
        SubString(temp,S,i,Sub.len);
        if(CompareString(Sub,temp)!=0) ++i;
        else return i;
    }
    return 0;
}
//串的基本操作
int main(void)
{
    MyString S1;
    S1.ch[0]=NULL;
    S1.ch[1]='w';
    S1.ch[2]='z';
    S1.len=2;
    MyString S2;
    S2.ch[0]=NULL;
    S2.ch[1]='z';
    S2.len=1;
    printf("%d\n",indexString(S1,S2));
    return 0;
}

2）串的朴素模式匹配算法

//串的朴素模式匹配算法
int Index(MyString S,MyString Sub)
{
    int i,j,k;//k用于定位S当前匹配到哪个位置,i,j分别用于S与Sub的活动定位
    k=1;
    i=k;
    j=1;
    while(S.len-k+1<=Sub.len)
    {
        if(S.ch[i]==Sub.ch[j])
        {
            ++i;
            ++j;
        }
        else
        {
            j=1;
            ++k;
            i=k;
        }
        if(j>Sub.len) return k;
        else return 0;
    }
}