《串的基本操作》

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1

typedef int Status;
#define MaxStrSize 255    //大小根据用户需要自己定义
typedef struct
{
    char ch[MaxStrSize+1];
    int length;
}SString;    //定义顺序串类型

int PartPosition(SString s1,SString s2,int k)
{/*从第K个位置开始扫描s1,当其元素值与s2的第一个元素
   想等时，判断它们之后的元素是否依次想等，直到s2结
   束为止。若都相同，则返回当前下标值，否则继续上述
   过程，直到s1扫描完为止。
 */
    int i,j;
    i = k-1;
    j = 0;
    //扫描s1的下标，数组下标从0开始
    while(i<s1.length && j<s2.length)
    {
        if(s1.ch[i] == s2.ch[j])
        {
            i++;
            j++;
            //继续使下标移向下一个字符
        }
        else
        {
            i=i-j+1;    //使i得下标回溯到原位置的下一位置。
            j=0;        //使j指向s2的第一个字符，再重新比较
        }
    }
    if(j>=s2.length)
        return i-j+1;        //表示s1中存在s2，返回其起始下标
    else 
        return -1;        //表示s1中不存在s2，返回-1
}

void main()
{
    int i,j,k;
    SString S,T;
    int wz[50];        //wz数组记录子串出现的位置
    i=0;
    printf("请输入主字符串：
");
    gets(S.ch);        //读入主串S
    printf("请输入模式串：
");
    gets(T.ch);
    S.length = strlen(S.ch);
    T.length = strlen(T.ch);
    k = 1;
    while(k<=S.length)
    {
        j = PartPosition(S,T,k);
        if(j<0)
            break;
        else
        {
            i++;
            wz[i]=j;        //不能写成j+1
            k=j+T.length;
            
        }
    }
    printf("
");
    printf("%d",i);
    printf("
");
    if(i==1)
    {
        printf("没有检索到需要的子串：");
    }
    else
    {
        printf("子串%s在主串中出现%d次
",T.ch,i);
        printf("%d次匹配位置分别为：",i);
        for(k=1;k<=i;k++)
            printf("%4d",wz[k]);
    }
    system("pause");
    printf("
");

}