链式串的模式匹配_链式串的模式匹配算法

#include <stdio.h>
#include <stdlib.h>
#include "str.h"


int Index(str f,str c)  //链式串的模式匹配算法 father  child
{
    str record=f;//record用来记录匹配前串在f中的位置
    str p,q;
    int cnt=1;
    for (p=c,q=record;p&&q;)
    {
        if (p->data==q->data)
        {
            p=p->next;
            q=q->next;
        }
        else
        {
            p=c;
            record=record->next;
            q=record;
            cnt++;
        }
    }
    if (p==NULL) return cnt;
    else return 0;
}


int main()
{
    int n,i;
    str a,b;
    a=b=NULL;
    while(1)
    {
        a=clear(a);
        b=clear(b);
        a=Createstr(a);
        b=Createstr(b);
        n=Index(b,a);
        for(i=0;i<n-1;i++)printf(" ");
        Print(a);
        printf("\n");
    }


    return 0;

}

头文件

#ifndef STR_H_INCLUDED
#define STR_H_INCLUDED


struct node
{
    char data;
    struct node*next;
};
typedef struct node* str;


str Initial(str t)              //初始化
{
    return NULL;
}


str Createstr(str t)            //创建串并返回
{
    printf("input the string\n");


    char ch;
    str tmp=NULL;
    str p;
    while((ch=getchar())!='\n')
    {
        tmp=(str)malloc(sizeof(struct node));
        tmp->data = ch;
        tmp->next = NULL;
        if(t==NULL) {t=tmp;p=t;continue;}
        p->next=tmp;
        p=p->next;
    }
    return t;
}


void Print(str t)           //输出串
{
    if(t==NULL) {printf("Empty\n");exit(0);}
    str p;
    for(p=t;p;p=p->next) printf("%c",p->data);
    printf("\n");
}


int length(str t)      //求串长
{
    int len=0;
    str tmp;
    for(tmp=t;tmp;tmp=tmp->next) len++;


    return len;
}


str clear(str t)
{
    str tmp;
    while(t!=NULL)
    {
        tmp=t;
        t=t->next;
        free(tmp);
    }
    return t;
}




str Concat(str T,str A,str B)
{
    if(T) T=clear(T);
    int i,len;
    str tmp,p,q;
    len = length(A);
    p=A;
    for(i=0;i<len;i++)
    {
        tmp=(str)malloc(sizeof(struct node));//建立新结点
        tmp->data=p->data;
        tmp->next=NULL;


        p=p->next;                           //取值点后移


        if(!T){T=tmp;q=T;continue;}           //第一次赋值
        q->next = tmp;                        //作为尾结点插入
        q=q->next;                            //q总是记下最后一个位置
    }


    p=B;
    len = length(B);
    for(i=0;i<len;i++)
    {
        tmp=(str)malloc(sizeof(struct node));
        tmp->data=p->data;
        tmp->next=NULL;
        p=p->next;


        q->next = tmp;  //作为尾结点插入
        q=q->next;      //q总是记下最后一个位置
    }
    return T;
}


str substr(str dst,str s,int pos,int len)
{
    if(pos+len>length(s)+1){printf("illegal\n");exit(0);}
    int i;
    str p,tmp;
    for(i=1;i<pos;i++) s=s->next;
    for(i=0;i<len;i++)
    {
        tmp=(str)malloc(sizeof(struct node));
        tmp->data = s->data;
        tmp->next = NULL;
        s=s->next;
        if(!dst)
        {
            dst=tmp;
            p=dst;
            continue;
        }
        p->next=tmp;
        p=p->next;
    }
    return dst;


}


#endif // STR_H_INCLUDED