串的模式匹配（BF算法）

【问题描述】

串的模式匹配算法BF的实现与应用。

【输入形式】

第一行输入主串s；

第二行输入模式串t；

输入串中均不包含空格字符。

【输出形式】

模式串在主串s中的出现的每一个位置序号。若一次都未匹配到，则输出0。

【样例输入1】

ababcabcacbab

ab

【样例输出1】

1 3 6 12

【样例输入2】

111113455113232342432432

11

【样例输出2】

1 2 3 4 10

【样例输入3】

fasdfdsfsadfdsdsagetgrdgfdgdf

2312

【样例输出3】

0

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>
 
#define INITSIZE 1000
#define INCRE 20
#define OK 1
#define ERROR 0
 
typedef struct{
  char* data;
  int length,stringsize;
}SqString;
 
//串初始化
int initString(SqString *S){
  S->data=(char *)malloc(INITSIZE*sizeof(char));
  if(!S->data)
    return 0;
  S->length=0;
  S->stringsize=INITSIZE;
  return 1;
}
 
//串赋值
int strAssign(SqString *s, char *str ){
    int i=0;
    while(*str)
        s->data[i++]=* str++;
    s->data[i]='\0';
    s->length=i;
    return 1;
}
//基本模式匹配算法
int index_bf(SqString *s,SqString *t,int start)
{
    int i=start-1,j=0;
    while(i<s->length&&j<t->length)   //依次比较主串s和子串t对应字符
        if(s->data[i]==t->data[j])   //对应字符相等，继续比较下一个字符
        {
            i++;
            j++;
        }
        else          //对应字符不相等，i和j回溯，开始下一趟比较
        {
            i=i-j+1;
            j=0;
        }
    if(j>=t->length)     //匹配成功，返回子串 t 在主串 s 中的位置
        return i-t->length+1;
    else
        return 0;
 
 
}
int main(){
       //利用模式匹配算法完成子串查找
 SqString S;
 SqString T;
    int pos=1,tmp=0;
    char str[1000];
    if(initString(&S)&&initString(&T))
    {
        scanf("%s",&str);
        strAssign(&S,&str[0]);
        scanf("%s",&str);
        strAssign(&T,&str[0]);
        while(pos<S.length)
        {
            pos=index_bf(&S,&T,pos);
            if(pos==0)break;
            printf("%d ",pos);
            tmp=1;
            pos++;
        }
        if(!tmp)printf("0");
        printf("\n");
    }
    return 0;
}