使用C语言解决字符串匹配问题的方法
最常想到的方法是使用KMP字符串匹配算法：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
intget_nextval(char*pattern,intnext[])
{
//getthenextvalueofthepattern
inti=0,j=-1;
next[0]=-1;
intpatlen=strlen(pattern);
while(i<patlen-1){
if(j==-1||pattern[i]==pattern[j]){
++i;
++j;
if(pattern[i]!=pattern[j])
next[i]=j;
else
next[i]=next[j];
}
else
j=next[j];
}
return(0);
}
intkmpindex(char*target,char*pattern,intpos)
{
inttari=pos,pati=0;
inttarlen=strlen(target),patlen=strlen(pattern);
int*next=(int*)malloc(patlen*sizeof(int));
get_nextval(pattern,next);
while(tari<tarlen&&pati<patlen){
if(pati==-1||target[tari]==pattern[pati]){
++tari;
++pati;
}else{
pati=next[pati];
}
}
if(next!=NULL)free(next);
next=NULL;
if(pati==patlen)
returntari-pati;
else
return-1;
}
intmain()
{
chartarget[50],pattern[50];
printf("imputthetarget:\n");
scanf("%s",target);
printf("imputthepattern:\n");
scanf("%s",pattern);
intans=kmpindex(target,pattern,0);
if(ans==-1)
printf("error\n");
else
printf("index:%d\n",ans);
return0;
}
练习题
题目描述：
读入数据string[]，然后读入一个短字符串。要求查找string[]中和短字符串的所有匹配，输出行号、匹配字符串。匹配时不区分大小写，并且可以有一个用中括号表示的模式匹配。如“aa[123]bb”，就是说aa1bb、aa2bb、aa3bb都算匹配。
输入：
输入有多组数据。
每组数据第一行输入n(1<=n<=1000)，从第二行开始输入n个字符串（不含空格），接下来输入一个匹配字符串。
输出：
输出匹配到的字符串的行号和该字符串（匹配时不区分大小写）。
样例输入：
4
Aab
a2B
ab
ABB
a[a2b]b
样例输出：
1Aab
2a2B
4ABB
ac代码
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#defineMAX1001
#defineLEN101
structstr
{
charname[101];
};
intmain()
{
structstrstrs[MAX];
structstrt[LEN];
inti,n,len,j,k,left,right,count,flag;
chartext[LEN],newtext[LEN];
while(scanf("%d",&n)!=EOF){
//接收数据
getchar();
for(i=0;i<n;i++){
scanf("%s",strs[i].name);
}
//接收文本串
getchar();
gets(text);
len=strlen(text);
for(i=left=right=0;i<len;i++){
if(text[i]=='['){
left=i;
}elseif(text[i]==']'){
right=i;
break;
}
}
count=right-left-1;
if(count<=0){//没有正则匹配
for(i=j=0;i<len;i++){
if(text[i]!='['&&text[i]!=']'){
newtext[j++]=text[i];
}
}
newtext[j]='\0';
for(i=0;i<n;i++){
if(strcasecmp(strs[i].name,newtext)==0){
printf("%d%s\n",i+1,strs[i].name);
}
}
}else{//需要正则匹配
for(j=1,k=0;j<=count;j++,k++){//构建文本数组
memset(t[k].name,'\0',sizeof(t[k].name));
for(i=0;i<left;i++){
t[k].name[i]=text[i];
}
t[k].name[i]=text[left+j];
strcat(t[k].name,text+right+1);
}
//正则匹配
for(i=0;i<n;i++){
for(j=flag=0;j<count;j++){
if(strcasecmp(strs[i].name,t[j].name)==0){
flag=1;
break;
}
}
if(flag){
printf("%d%s\n",i+1,strs[i].name);
}
}
}
}
return0;
}
/**************************************************************
Problem:1165
User:wangzhengyi
Language:C
Result:Accepted
Time:0ms
Memory:948kb
****************************************************************/