字符串操作.cpp

字符串模式匹配

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXSIZE 100

//字符串的输入
 void input(char a[])
{char c;
int i=0,j=0;
while((c=getchar())!='\n')
{a[i]=c;
i++;}
a[i]='\0';
}


 //查找目的串的位置
int find(char s[],char d[],int pos)
{int i;
int j=0;
i=pos-1;
int n;
while(s[i]!='\0' && d[j]!='\0')
{if(s[i]==d[j])
{i++;j++;}
else
{i=i-j+1;
j=0;}
}
if(d[j]=='\0')
{n=i-strlen(d)+1;
//printf("%d\n",n);
return n;
}


else return -1;
}

//用next[]数组存放模式串的next值
void getnext(char d[],int next[])
{int i=0;
int j;
next[0]=-1;
j=-1;
while(i<strlen(d))
{if(j==-1||d[i]==d[j])
{++i;++j;next[i]=j;
}
else j=next[j];
}

}



//KMP方法查找目的串的位置
int find2(char s[],char d[], int pos)
{int i,j;
int n;
	i=pos-1;
j=0;
int n1=strlen(d);
int next[100];
getnext(d,next);

while(s[i]!='\0' && d[j]!='\0')
{if(j==-1||s[i]==d[j])
{i++;j++;}
else j=next[j];
}
if(d[j]=='\0')
{n=i-strlen(d)+1;
//printf("%d\n",n);
return n;
}
else return -1;
}

void deletestring( char s[],int pos,int length)
{ int i,j;
i=pos-1;

for(j=i+length;j<=strlen(s);j++)
s[j-length]=s[j];
//printf("%s\n",s);
}



void stringoperate()
{char s[MAXSIZE],d[10];
char c;
int i=0,j=0;
int pos=1;
int flag=1;
int n;
int length;
c=getchar();
printf("输入原操作串\n");
//input(s);
gets(s);
//c=getchar();
printf("输入目的操作串\n");
//input(d);
gets(d);
length=strlen(d);
//printf("%s\n",s);
//puts(s);

//puts(d);
//printf("%s\n",d);

while(flag)
{//n=find(s,d,pos);
	n=find2(s,d,pos);
if(n==-1)
{
	//printf("没有该子串了最后结果为\n");
	printf("最后结果为：\n");
printf("\n%s\n",s);
break;
}
else 
{pos=n;
//printf("%d\n",pos);
	deletestring(s,pos,length);
//printf("%s\n",s);
//break;
}
}



}
void main()
{int n;
while(1)
{printf("输入选择的序号1表示继续做，0表示退出\n");
scanf("%d",&n);
if(n==0)
break;
switch(n)
{case 1: stringoperate();break;
default: printf("error\n");break;
}
}
}