Skip to content
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 - ii 表示字符在模式串中的索引)
e1
x6
a5
m4
p3
l2
其他字符8(即 m+1,表示不在模式串中的字符)

Step 2: 匹配过程

我们将模式串从主串的起始位置开始对齐,逐步匹配。如果发现不匹配,我们根据偏移表决定滑动步数,并继续下一次比较。


第一次匹配

  1. 初始对齐:

    主串:  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'):第一字符就不匹配。
  2. 滑动模式串:

    • 查看当前窗口后一个字符 T[7] = 's'
    • 偏移表中没有字符 's',滑动 m + 1 = 7 + 1 = 8
    • 新窗口的起始索引为 0 + 8 = 8

第二次匹配

  1. 对齐:

    主串:  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'):第一字符不匹配。
  2. 滑动模式串:

    • 查看当前窗口后一个字符 T[15] = 'e'
    • 偏移表中字符 'e' 的偏移值为 1
    • 滑动 1 个位置。
    • 新窗口的起始索引为 8 + 1 = 9

第三次匹配

  1. 对齐:

    主串:  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'):第一字符不匹配。
  2. 滑动模式串:

    • 查看当前窗口后一个字符 T[16] = 'e'
    • 偏移表中字符 'e' 的偏移值为 1
    • 滑动 1 个位置。
    • 新窗口的起始索引为 9 + 1 = 10

第四次匹配

  1. 对齐:

    主串:  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'):第一字符不匹配。
  2. 滑动模式串:

    • 查看当前窗口后一个字符 T[17] = 'e'
    • 偏移表中字符 'e' 的偏移值为 1
    • 滑动 1 个位置。
    • 新窗口的起始索引为 10 + 1 = 11

第五次匹配

  1. 对齐:

    主串:  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'):第一字符不匹配。
  2. 滑动模式串:

    • 查看当前窗口后一个字符 T[18] = 'e'
    • 偏移表中字符 'e' 的偏移值为 1
    • 滑动 1 个位置。
    • 新窗口的起始索引为 11 + 1 = 12

第六次匹配

  1. 对齐:

    主串:  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'):第一字符不匹配。
  2. 滑动模式串:

    • 查看当前窗口后一个字符 T[19] = 'e'
    • 偏移表中字符 'e' 的偏移值为 1
    • 滑动 1 个位置。
    • 新窗口的起始索引为 12 + 1 = 13

第七次匹配

  1. 对齐:

    主串:  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'):匹配!
  2. 全部字符匹配成功!返回起始索引 13


总结

模式串 P = "example" 在主串 T = "here is a simple example" 中的匹配位置为 索引 13

希望这个详细的对齐和比较过程对你理解 Sunday 算法有所帮助!如果有进一步的问题,欢迎提问!