#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#define MaxSize 10
typedef struct SString
{
char ch[MaxSize];
int length;
}SString;
InitSString(SString* S);//初始化串
StrAssign(SString* S,char ch[]);//赋值操作
SString* SubString(SString*Sub,SString*S,int pos,int len);//求子串,用Sub返回S中第pos个字符起长度为len的子串
int StrCompare(SString S, SString L);//比较两个串的大小,返回<0则L长,反知
int Index(SString S, SString L);//定位操作,若主串S中存在与L相同的子串,则返回他在主串S中第一次出现的位置
InitSString(SString* S)//初始化串
{
S->length = 0;
}
StrAssign(SString* S,char arr[])//赋值操作(创建)
{
int i = 0;
int x = sizeof(arr) / sizeof(arr[0]);
if (MaxSize < x)
printf("超出了串的长度,赋值失败\n");
for (i = 0; arr[i] != '\0'; i++)
{
S->ch[i] = arr[i];
}
S->length = i;
}
SString* SubString(SString* Sub, SString* S, int pos, int len)//求子串,用Sub返回S中第pos个字符起长度为len的子串
{
if (pos + len - 1 > S->length)
printf("该字符串超过了界限\n");
else
{
for (int i = pos; i <= pos + len; i++)
{
Sub->ch[i-pos+1] = S->ch[i];
}
Sub->length = len;
printf("返回成功\n");
return Sub;
}
}
int StrCompare(SString S, SString L)//比较两个串的大小,返回<0则L长,反知
{
for (int i = 0; i < S.length && i < L.length; i++)
{
if (S.ch[i] != L.ch[i])
return S.ch[i] - L.ch[i];
}
return S.length - L.length;
}
int Index(SString S, SString L)//定位操作,若主串S中存在与L相同的子串,则返回他在主串S中第一次出现的位置
{
int i = 1, n = StrLength(S), m = Strlength(L);
SString sub;
while(i <= n - m + 1)
{
SubString(&sub,&S,i,m);//依次取S中长度为m的子串
if (StrCompare(L, sub) != 0)
{
i++;
}
else return i;
}
pritnf("不存在相同的子串\n");
}
朴素模式匹配算法
int Index(SString S, SString L)//朴素模式匹配算法
{
int i = 1, j = 1;
while (i < S.length && j < L.length)
{
if (S.ch[i] == L.ch[i])
{
i++;
j++;
}
else
{
i = i - j + 2;//i指向下一个子串的首位置
j = 1;
}
}
if (j > L.length)//因为j指向下一个元素,若超过了l的长度则说明前面的元素均相等
{
printf("匹配成功\n");
return j - L.length;
}
else
{
printf("不存在子串,匹配失败\n");
}
}