第2章第3节练习题1 串的模式匹配(Naive)

问题描述

设有主串s和子串t,子串t的定位就是要在主串s中找到一个与子串t相等的子串。
通常把主串s称为目标串,把子串t称为模式串,因此定位也称作模式匹配。
模式匹配成功是指在目标串s中找到一个模式串t；不成功则指目标串s中不存在模式串t。

算法描述

本算法与第1章第2节练习题14 判断子序列 本质相同，那么运用同样的算法也可以解决该问题。
首先对s和t同时进行访问，如果t中的元素有一个与s不匹配，那么对字符串s和字符串t的下标进行重置，s的下标重置为与t开始相比的下一个下标，t的下标置0。
如果s或t有一个已经访问结束，那么判断t是否访问结束。如果是，则标志已经访问完成；如果不是，则表示没有在s中找到子串t。

算法思想

int FindSub(String* S, String* T){
int i=0,j=0;
while(i<S->length&&j<T->length){
if(S->data[i]==T->data[j]){
            i++;
            j++;
        }else{
            i=i-j+1;
            j=0;
        }
    }
if(j==T->length){
return 0;
    }else{
return -1;
    }
}

具体代码见附件。

---

附件

#include<stdio.h>
#include<stdlib.h>

#define MaxSize 100
typedef char ElemType;
typedef struct{
    ElemType data[MaxSize];
int length;
}String;

void StrCreat(String*);
void Print(String*);
int FindSub(String*,String*);


int main(int argc,char* argv[])
{
    String *s;
    s=(String*)malloc(sizeof(String));
    StrCreat(s);

    String *t;
    t=(String*)malloc(sizeof(String));
    StrCreat(t);

int flag=FindSub(s,t);
if(flag==0){
printf("t is subString of s!\n");
    }else{
printf("t is not subString of s!\n");
    }

return 0;
}
//创建串
void StrCreat(String* S){
char x;
    S->length=0;
printf("Input String_S(End of '#'!):\n");
scanf("%c",&x);
while(x!='#'){
        S->data[S->length++]=x;
scanf("%c",&x);
    }
    getchar();
}
//模式匹配，寻找s中是否存在子串t
int FindSub(String* S, String* T){
int i=0,j=0;
while(i<S->length&&j<T->length){
if(S->data[i]==T->data[j]){
            i++;
            j++;
        }else{
            i=i-j+1;
            j=0;
        }
    }
if(j==T->length){
return 0;
    }else{
return -1;
    }
}
//打印所有串元素
void Print(String* S){
for(int i=0;i<S->length;i++){
printf("%c",S->data[i]);
    }
printf("\n");
}