#include <stdlib.h>
#include <string.h>
//定義順序串
#define MaxSize 30
typedef struct
{
char data[MaxSize];
int len;
}SqString;
//串的子串個數(順序串)
int SubNum(SqString s)
{
int n;
n=1+(s.len+1)*s.len/2;
return n;
}
//串的匹配查詢(順序串)
int StrIndex(SqString s,SqString t)//s為主串,t為模式串
{
int i=0,j=0;
while(i<s.len&&j<t.len)//是否到末尾
{
if(s.data[i]==t.data[j])//主串與模式串逐壹匹配
{
i++;
j++;
}
else //否則，回溯重新開始下壹次匹配
{
i=i-j+1; //主串從下壹個位置開始
j=0; //模式串從頭開始
}
}
if(j>=t.len) //如果匹配成功
return (i-t.len); //返回主串第壹個下標
else
return -1; //匹配失敗,返回-1
}
//串的連接
//將串1和串2合並成新串,原串保留
int Concat(SqString str1,SqString str2,SqString &str,int maxlen)
{
int i;
if(str1.len + str2.len > maxlen)//長度之和不能超過maxlen
{
printf("兩串合並後的長度超過規定長度.\n");
return 0;
}
else
{
for(i=0;i<str1.len;i++)
str.data[i]=str1.data[i];//將串1復制給新串
for(i=0;i<str2.len;i++)
str.data[str1.len+i]=str2.data[i];//將串2復制給新串
str.data[str1.len+i]='\0';//置結束標誌
str.len=str1.len+str2.len;//計算長度和
}
return 1;
}
//串的替換
//串1從第i字符開始的j個字符用串2替換，生成新串
int Replace(SqString str1,int i,int j,SqString str2,SqString &str)
{
int m,n;
if(j!=str2.len)//如果替換長度不等於串2,退出
{
printf("替換長度與串2不等.\n");
return 0;
}
if(i+j-1<=str1.len)//i開始j的長度在串1之內
{
for(m=0;m<i-1;m++)//拷貝串1中0到i-1之間字符
str.data[m]=str1.data[m];
for(n=0;n<str2.len;n++)//拷貝串2的所有字符
str.data[m++]=str2.data[n];
for(n=i+j-1;n<str1.len;n++)//拷貝串1從i+j-1之後的所以字符
str.data[m++]=str1.data[n];
str.data[m]='\0';//置結束標誌
str.len=m;//置新串長度
}
else //超過，置長度為0
{
str.data[0]='\0';//置結束標誌
str.len=0;
}
return 1;
}
//串中刪除字符ch
void Delch(SqString &str,char ch)
{
int i,j;
for(i=0;i<str.len;i++)//遍歷元素
{
while(str.data[i]==ch)//如果為ch,將後面元素前移,直到不等於ch為止
{
for(j=i;j<str.len;j++)
str.data[j]=str.data[j+1];//將後面元素前移
str.len=str.len-1;//長度減壹
}
}
}
//刪除串中從第i個字符開始j個字符
void Delsub(SqString &str,int i,int j)
{
int k;
if(i+j-1>str.len)
{
printf("刪除子串長度超過主串長度.\n");
}
else
{
for(k=i+j-1;k<str.len;k++)//遍歷元素
{
str.data[k-j]=str.data[k];//後面元素前移
}
str.len=str.len-j; //長度減少
str.data[str.len]='\0'; //置末尾結束
}
}
//串逆序
void ReverseSq(SqString &str)
{
int i,j;
char t;
i=0;
j=str.len-1;//首尾調換
while(i<j)
{
t=str.data[i];
str.data[i]=str.data[j];
str.data[j]=t;
i++;
j--;
}
}
//子串只有壹個通配符?,可以代表任意壹個字符，返回匹配子串第壹次出現位置
int Patten_index(SqString &subs,SqString str)
{
int i,j,k;
for(i=0;i<str.len;i++)
{
for(j=i,k=0;(str.data[j]==subs.data[k])||(subs.data[k]=='?');j++,k++)
if(subs.data[k+1]=='\0')
return(i+1);
}
return -1;
}
//求最長等值子串串頭位置和子串
void EqsubString(SqString str)
{
int i,j;
int pos,max,count;
pos=0;
max=1;
for(i=0,j=1;str.data[i]!='\0'&&str.data[j]!='\0';i=j,j++)
{
count=1;
while(str.data[i]==str.data[j])
{
j++;
count++;
}
if(count > max)
{
max=count;
pos=i;
}
}
if(max>1)
{
printf("位置為:%d的最大等值子串:",pos+1);
for(i=pos;i<pos+max;i++)
printf("%c",str.data[i]);
}
else
printf("無最大等值子串.");
printf("\n");
}
int main()
{
SqString str1,str2;
SqString str;
strcpy(str1.data,"abcdefghijkl");
str1.len=strlen(str1.data);
strcpy(str2.data,"aaad");
str2.len=strlen(str2.data);
printf("str1=%d,%s\nstr2=%d,%s\n",str1.len,str1.data,str2.len,str2.data);
//1 串的匹配
printf("串的匹配\n");
if(StrIndex(str1,str2)!=-1)
printf("匹配成功!\n");
else
printf("匹配失敗!\n");
printf("\n");
//2 串的連接
printf("串的連接\n");
if(Concat(str1,str2,str,MaxSize))
printf("合並後的新串%d,%s\n",str.len,str.data);
else
printf("合並出錯.\n");
printf("\n");
//3 串的替換
printf("串的替換\n");
if(Replace(str1,9,4,str2,str))
printf("替換後的新串長度%d,%s\n",str.len,str.data);
printf("\n");
//4 子串的個數
printf("子串的個數\n");
printf("%s子串個數為:%d\n",str.data,SubNum(str));
printf("\n");
//5 刪除壹個字符
printf("刪除壹個字符'b'\n");
printf("原串%s\n",str.data);
Delch(str,'b');
printf("刪除後串長度%d,%s\n",str.len,str.data);
printf("\n");
//6 串中從第i個字符開始j個字符
printf("刪除從第2個位置刪除3個字符\n");
Delsub(str,2,3);
printf("刪除子串後串長度%d,%s\n",str.len,str.data);
printf("\n");
//7 串逆序
printf("串逆序\n");
ReverseSq(str);
printf("串逆序長度%d,%s\n",str.len,str.data);
printf("\n");
//8 子串通配符?匹配
printf("子串通配符?匹配:g?\n");
int x;
SqString subs;
strcpy(subs.data,"g?");
subs.len=strlen(subs.data);
if((x=Patten_index(subs,str))>0)
printf("在%d 匹配成功!\n",x);
else
printf("匹配失敗!\n");
printf("\n");
//9 求最長等值子串串頭位置和子串
printf("求最長等值子串串頭位置和子串\n");
EqsubString(str);
printf("\n");
return 0;
}