typedef struct
{int i,j;//矩阵的行列int v;//矩阵的值
}SPNode;
typedef struct
{int mu,nu,tu;//矩阵的行列与非零值SPNode date[Max_size];
}SPMatrix;
//初始化矩阵
void InitSPNode(SPMatrix* a)
{int k,i,j,v;k=0;i=0;j=0;a->mu=0;a->nu=0;while(i!=-1&&j!=-1){printf("请输入(行 列 值):");scanf("%d%d%d",&i,&j,&v);a->date[k].i=i;a->date[k].j=j;a->date[k].v=v;if(i>(a->mu)){a->mu=i;}if(j>(a->nu)){a->nu=j;}k++;}a->tu=k-1;
}
//打印矩阵
void ShowMatrix(SPMatrix* c)
{int m=0;int n=0;int t=0;for(m=0;m<=(c->mu);m++){for(n=0;n<=(c->nu);n++){//如果打印的行列等于数组里存储的打印该值if(m==(c->date[t].i)&&n==(c->date[t].j)){printf("%d ",c->date[t].v);t++;}//其他情况打印0else{printf("0 ");}}printf("\n");}
}
//矩阵的转置
void TransposeMatrix(SPMatrix* a,SPMatrix* b)
{int t=0;int m=0;int n=0;b->mu=a->nu;b->nu=a->mu;b->tu=a->tu;for(n=0;n<=(a->nu);n++){//遍历矩阵的非零元素以a的列进行循环处理for(m=0;m<=(a->tu);m++){if(a->date[m].j==n){b->date[t].i=a->date[m].j;b->date[t].j=a->date[m].i;b->date[t].v=a->date[m].v;t++;}}}
}

#define MAX_num 100
typedef struct
{char date[MAX_num];int len;
}SString;
void GetNext(SString* a,int next[])
{int i=1;int j=0;next[1]=0;while(i<a->len){if(a->date[i]==a->date[j]||j==0){next[++i]=++j;}else{j=next[j];}}
}
int IndexKmp(SString* a,SString* b,int pos,int* next)
{int i=pos;int j=1;while(i<=a->len&&j<=b->len){if(j==0||a->date[i]==b->date[j]){i++;j++;}else{j=next[j];}}if(j>b->len){return i-b->len;}elsereturn 0;
}
int main()
{int locate;int next[MAX_num];SString s;SString t;printf("请输入主串:");scanf("%s",s.date+1);s.len=strlen(s.date)-1;printf("请输入子串:");scanf("%s",t.date+1);t.len=strlen(t.date)-1;GetNext(&t,next);locate=IndexKmp(&s,&t,0,next);printf("匹配位置;%d\n",locate);return 0;
}