c
#include <stdio.h>
#include <string.h>
#define MAX_CHAR 256
void rev(char *t)
{
char* start=t;
char* end=t+strlen(t)-1;
while(start<end)
{
char temp=*start;
*start=*end;
*end=temp;
start++;
end--;
}
}
void setTable(char* p,char table[])
{
int pSize=strlen(p);
// 初始化table为pSize+1,长度的下一位
for(int i=0;i<MAX_CHAR;i++)
{
table[i]=pSize+1;
}
// 初始化table中的pSize的右侧位置=长度-下标
for(int j=0;j<pSize;j++)
{
table[p[j]]=pSize-j;
}
}
int sunday(char* t,char* p)
{
char table[MAX_CHAR];
int tSize=strlen(t);
int pSize=strlen(p);
setTable(p,table);
// 如果字符串t<字符串p,直接结束
if(tSize<pSize)
{
return -1;
}
// 模式串对齐索引
int i=0;
// 如果匹配到最后,结束
while(i<=tSize-pSize)
{
// m每轮都为0
int j=0;
// j只能到p的长度,否则匹配无意义
while (j<pSize && t[i+j]==p[j]) {
j++;
}
// 匹配成功
if(j==pSize)
{
return i;
}
// 匹配失败,i向后移动到
if(i+pSize<tSize)
{
// 下一个要匹配的字符
char next=t[i+pSize];
// 移动位数
i+=table[next];
}else
{
// 到达末尾
break;
}
}
return -1;
}
// 主函数测试
int main() {
char text[] = "hereisasimpleexample";
char pattern[] = "eex";
// rev(text);
// rev(pattern);
// 返回值需要加上pSize
int result = sunday(text, pattern);
if (result != -1) {
printf("模式串首次出现在主串中的位置:%d\n", result);
} else {
printf("模式串未出现在主串中。\n");
}
return 0;
}
好的!我们详细分步说明 Sunday
算法的比较过程,并且清晰标记每次模式串的位置、主串的相应窗口及字符比较的细节。我们使用以下示例:
示例
- 主串(文本):
T = "here is a simple example"
- 模式串(子串):
P = "example"
我们目标是找到主串中模式串第一次出现的位置。
Step 1: 构建偏移表
我们先构建模式串的偏移表。模式串 P = "example"
的长度为 m = 7
,我们从右到左遍历模式串,为每个字符计算相对于模式串末尾的偏移值。
字符 | 偏移值(m - i ,i 表示字符在模式串中的索引) |
---|---|
e | 1 |
x | 6 |
a | 5 |
m | 4 |
p | 3 |
l | 2 |
其他字符 | 8(即 m+1 ,表示不在模式串中的字符) |
Step 2: 匹配过程
我们将模式串从主串的起始位置开始对齐,逐步匹配。如果发现不匹配,我们根据偏移表决定滑动步数,并继续下一次比较。
第一次匹配
初始对齐:
主串: h e r e i s a s i m p l e e x a m p l e 模式串: e x a m p l e 对齐位置索引:0
- 比较字符:
T[0] ('h') != P[0] ('e')
:第一字符就不匹配。
- 比较字符:
滑动模式串:
- 查看当前窗口后一个字符
T[7] = 's'
。 - 偏移表中没有字符
's'
,滑动m + 1 = 7 + 1 = 8
。 - 新窗口的起始索引为
0 + 8 = 8
。
- 查看当前窗口后一个字符
第二次匹配
对齐:
主串: h e r e i s a s i m p l e e x a m p l e 模式串: e x a m p l e 对齐位置索引:8
- 比较字符:
T[8] ('a') != P[0] ('e')
:第一字符不匹配。
- 比较字符:
滑动模式串:
- 查看当前窗口后一个字符
T[15] = 'e'
。 - 偏移表中字符
'e'
的偏移值为1
。 - 滑动
1
个位置。 - 新窗口的起始索引为
8 + 1 = 9
。
- 查看当前窗口后一个字符
第三次匹配
对齐:
主串: h e r e i s a s i m p l e e x a m p l e 模式串: e x a m p l e 对齐位置索引:9
- 比较字符:
T[9] ('s') != P[0] ('e')
:第一字符不匹配。
- 比较字符:
滑动模式串:
- 查看当前窗口后一个字符
T[16] = 'e'
。 - 偏移表中字符
'e'
的偏移值为1
。 - 滑动
1
个位置。 - 新窗口的起始索引为
9 + 1 = 10
。
- 查看当前窗口后一个字符
第四次匹配
对齐:
主串: h e r e i s a s i m p l e e x a m p l e 模式串: e x a m p l e 对齐位置索引:10
- 比较字符:
T[10] ('i') != P[0] ('e')
:第一字符不匹配。
- 比较字符:
滑动模式串:
- 查看当前窗口后一个字符
T[17] = 'e'
。 - 偏移表中字符
'e'
的偏移值为1
。 - 滑动
1
个位置。 - 新窗口的起始索引为
10 + 1 = 11
。
- 查看当前窗口后一个字符
第五次匹配
对齐:
主串: h e r e i s a s i m p l e e x a m p l e 模式串: e x a m p l e 对齐位置索引:11
- 比较字符:
T[11] ('m') != P[0] ('e')
:第一字符不匹配。
- 比较字符:
滑动模式串:
- 查看当前窗口后一个字符
T[18] = 'e'
。 - 偏移表中字符
'e'
的偏移值为1
。 - 滑动
1
个位置。 - 新窗口的起始索引为
11 + 1 = 12
。
- 查看当前窗口后一个字符
第六次匹配
对齐:
主串: h e r e i s a s i m p l e e x a m p l e 模式串: e x a m p l e 对齐位置索引:12
- 比较字符:
T[12] ('p') != P[0] ('e')
:第一字符不匹配。
- 比较字符:
滑动模式串:
- 查看当前窗口后一个字符
T[19] = 'e'
。 - 偏移表中字符
'e'
的偏移值为1
。 - 滑动
1
个位置。 - 新窗口的起始索引为
12 + 1 = 13
。
- 查看当前窗口后一个字符
第七次匹配
对齐:
主串: h e r e i s a s i m p l e e x a m p l e 模式串: e x a m p l e 对齐位置索引:13
- 比较字符:
T[13] ('e') == P[0] ('e')
:匹配!T[14] ('x') == P[1] ('x')
:匹配!T[15] ('a') == P[2] ('a')
:匹配!T[16] ('m') == P[3] ('m')
:匹配!T[17] ('p') == P[4] ('p')
:匹配!T[18] ('l') == P[5] ('l')
:匹配!T[19] ('e') == P[6] ('e')
:匹配!
- 比较字符:
全部字符匹配成功!返回起始索引
13
。
总结
模式串 P = "example"
在主串 T = "here is a simple example"
中的匹配位置为 索引 13。
希望这个详细的对齐和比较过程对你理解 Sunday 算法有所帮助!如果有进一步的问题,欢迎提问!