#include<stdio.h>

#include<windows.h>

#define maxsize 100

typedef struct //非紧缩格式的顺序串的定义
{
char data[maxsize];
int length;

}sqstring;

void strassign(sqstring &s) //将字符串复制给串
{
char a[100];
int i;
getchar();
printf("请输入一个字符串:");
gets(a);
for(i=0;a[i]!='\0';i++)
s.data[i]=a[i];
s.length=i;

}

void dispstr(sqstring s) //输出串的所有元素
{
int i;
if(s.length<=0)
printf("串为空，输出失败!\n");
else
{
if(s.length>0)
{
for(i=0;i<s.length;i++)
printf(" %c",s.data[i]);
}
printf("\n");
}

}

void strcopy(sqstring &s,sqstring t) //串与串的复制
{
int i;
for(i=0;i<t.length;i++)
s.data[i]=t.data[i];
s.length=t.length;

}

int strequal(sqstring s) //判断串相等
{
sqstring t;
strassign(t);
int i,m=1;
if(s.length!=t.length)
m=0;
else
for(i=0;i<s.length;i++)
if(s.data[i]!=t.data[i])
m=0;
if(m==1)
printf("串相等\n");
else
printf("串不相等\n");
return m;

}

void strlength(sqstring s) //求串长
{
printf("s.length=%d\n",s.length);
}
sqstring concate(sqstring s) //串的连接
{
sqstring t,str;
strassign(t);
int i,j;
if(s.length==0)
str.length=0;
else
{
str.length=s.length+t.length;
for(i=0;i<s.length;i++)
str.data[i]=s.data[i];
for(i=0;i<t.length;i++)
str.data[s.length+i]=t.data[i];
}
return str;

}

void substr(sqstring s) //求子串
{
sqstring str;
int i,j,k;
printf("请输入第i个字符开始的连续j个字符组成的子串的i、j值\n");
printf("i=");
scanf("%d",&i);
printf("j=");
scanf("%d",&j);
if(s.length==0)
printf("串为空!\n");
else if(i<=0||i>s.length||j<0||i+j-1>s.length)
printf("输入错误!\n");
else
{
str.length=j;
for(k=i-1;j>0;j--,k++)
str.data[k-i+1]=s.data[k];
printf("所求子串为:");
dispstr(str);
}

}

void insstr(sqstring &s) //将串s2插到串s的第i个字符中
{
sqstring s2,str;
int i,j;
str.length=0;
strassign(s2);
printf("请输入需把串插入的位置:");
scanf("%d",&i);
if(i<0||i>s.length+1)
printf("输入错误!\n");
else
{
for(j=0;j<i-1;j++)
str.data[j]=s.data[j];
for(j=0;j<s2.length;j++)
str.data[j+i-1]=s2.data[j];
for(j=i-1;j<s.length;j++)
str.data[j+s2.length]=s.data[j];
str.length=s.length+s2.length;
strcopy(s,str);
printf("插入后的串为:");
dispstr(s);
}

}

void delstr(sqstring &s) //从串s中删去第i个字符开始的长度为j的子串
{
int i,j,k;
printf("删除第i个字符开始的长度为j的子串\n");
printf("i=");
scanf("%d",&i);
printf("j=");
scanf("%d",&j);
if(s.length==0)
printf("串为空!\n");
else if(i<=0||i>s.length||i+j-1>s.length)
printf("输入错误!\n");
else
{
k=j;
for(;j>=0;j--,i++)
s.data[i-1]=s.data[i+k-1];
s.length=s.length-k;
printf("删除后的串为: ");
dispstr(s);
}

}

void repstr(sqstring &s) //将第i个字符开始的j个字符够成的子串用串t替换
{
sqstring t,str;
int i,j,k;
printf("s串中将第i个字符开始的j个字符够成的子串用串t替换\n");
printf("i=");
scanf("%d",&i);
printf(" j=");
scanf("%d",&j);
strassign(t);
if(i<0||i>s.length||i+j-1>s.length)
printf("输入错误!\n");
else
{
str.length=0;
for(k=0;k<i-1;k++)
str.data[k]=s.data[k];
for(k=0;k<t.length;k++)
str.data[k+i-1]=t.data[k];
for(k=i+j-1;k<s.length;k++)
str.data[k-j+t.length]=s.data[k];
str.length=s.length+t.length-j;
strcopy(s,str);
printf("替换后的串为:");
dispstr(s);
}

}

void index(sqstring s,sqstring t) //串的模式匹配(bf算法)
{
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) 
printf("匹配成功在第%d位\n\n",i-t.length+1);
else 
printf("匹配不成功!\n");

}

void main()
{
sqstring s,t;
int m;
while(1)
{
printf("请选择:");
printf("1 将字符串复制给串s\n");
printf(" 2 串与串的复制\n");
printf(" 3 判断串相等\n");
printf(" 4 求串的长度\n");
printf(" 5 串的连接\n");
printf(" 6 求子串\n");
printf(" 7 将串s2插到串s的第i个字符位置\n");
printf(" 8 从串s中删去从第i个字符开始的长度为j的子串\n");
printf(" 9 将第i个字符开始的j个字符够成的子串用串t替换\n");
printf(" 10 串的模式匹配\n");
printf(" 11 输出串的所有元素\n");
printf(" 12 退出\n");
scanf("%d",&m);
switch(m)
{
case 1:strassign(s);
printf("复制成功\n");break;
case 2:strassign(t);
strcopy(s,t);
printf("复制成功\n");break;
case 3:strequal(s);break;
case 4:strlength(s);break;
case 5:dispstr(concate(s));break;
case 6:substr(s);break;
case 7:insstr(s);break;
case 8:delstr(s);break;
case 9:repstr(s);break;
case 10:strassign(t);index(s,t);break;
case 11:printf("s: ");dispstr(s);break;
case 12:printf("谢谢使用!\n");exit(0);break;
default:printf("输入错误!\n");
}
}
}