数据结构例程——串的模式匹配(Brute-Force算法)

本文针对数据结构基础系列网络课程(4):串中第5课时串的模式匹配(Brute-Force算法)

问题:模式匹配,设有主串s和子串t,在主串s中找到一个与子串t相等的子串。
数据结构例程——串的模式匹配(Brute-Force算法)

解答:(头文件sqstring.h见顺序串算法库

#include <stdio.h>
#include "sqString.h"

int index(SqString s,SqString 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(i-t.length);         //返回匹配的第一个字符的下标
    else
        return(-1);             //模式匹配不成功
}
int main()
{
    SqString s,t;
    StrAssign(s,"ababcabcacbab");
    StrAssign(t,"abcac");
    printf("s:");
    DispStr(s);
    printf("t:");
    DispStr(t);
    printf("位置:%d\n",index(s,t));
    return 0;
}
上一篇:dart设计模式之外观,享元,代理模式


下一篇:数据结构例程——串的模式匹配(KMP算法)