欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

对字符串进行匹配和替换系统

程序员文章站 2024-03-18 12:00:16
...

帮同学写的一个课程设计,没时间了。
匹配当然是用KMP最好使了,其余的没什么了。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<stdbool.h>
#define N 100
#define COUNT 10


void getNext(char * b);
int KMP(char *a,char *b,int start);


int num=0;
int next[N];
char a[N],b[N],c[N],d[N];

int main(){

     showtitle();

     printf("***请选择指令***\n");
     int n ;
     while(scanf("%d",&n)!=EOF){

        switch(n){

        case 1:
            filemainstring(COUNT);
            printf("\n***请选择指令***\n");
            break;
        case 2:
            filesubstring(COUNT);
            printf("\n***请选择指令***\n");
            break;
        case 3:
            getNext(b);
            showNext(b);
            printf("\n***请选择指令***\n");
            break;
        case 4:
            substring(a,b,0);
            printf("\n***请选择指令***\n");
            break;
        case 5:
            printf("请输入要替换的子串:\n");
            scanf("%s",b);
            getchar();
            printf("请输入要替换成的子串\n");
            scanf("%s",c);
            replace(a,b,c,0);
            printf("\n***请选择指令***\n");
            break;
        case 6:
            showtitle();
            break;
        case 7:
             printf("欢迎下次再来,拜拜,爱你呦(小罗结束语)\n");
              n = -1;
             break;
        default :
            printf("指令无效,请重新输入\n");
            break;
        }
        if(n==-1)
            break;
     }

    return 0;
}
//显示菜单
void showtitle(){
    printf("********************************************************\n");
    printf("*                    欢迎来到小罗查找                  *\n");
    printf("********************************************************\n\n");
    printf("1.从文件导入主串\t\t2.从文件导入模式串\n\n");
    printf("3.计算模式串的next\t\t4.对子串进行KMP查找\n\n");
    printf("5.对字串进行替换\t\t6.显示菜单\n\n"
           "7.结束查询,退出查找系统\n\n");

}


//从文件选择主串
void filemainstring(int count){
    char str[count][N];
    FILE *fp;
    if((fp = fopen("D://mainstring.txt","r"))==NULL){
        printf("File not open\n");
        exit(1);
    }
    for(int i = 0;i<count;i++){

        fscanf(fp,"%s\n",str[i]);
    }
    fclose(fp);
    printf("请选择主串\n");
    for(int i = 0;i<count;i++){
       printf("%d.%s\n",i+1,str[i]);
    }
    printf("请输入主串编号\n");
    int n ;
    scanf("%d",&n);
    int i =0, j=0 ;
    strcpy(a,str[n-1]);
    printf("选择主串成功\n");
}



//从文件选择模式串
void filesubstring(int count){
    char str[count][N];
    FILE *fp ;
    if((fp = fopen("D://substring.txt","r"))==NULL){
        printf("File not open\n");
        exit(1);
    }
    for(int i = 0;i<count;i++){

        fscanf(fp,"%s\n",str[i]);
    }
    fclose(fp);
    printf("请选择模式串\n");
    for(int i = 0;i<count;i++){
       printf("%d.%s\n",i+1,str[i]);
    }
    printf("请输入模式串编号\n");
    int n ;
    scanf("%d",&n);
    int i =0, j=0 ;
    strcpy(b,str[n-1]);
    printf("选择模式串串成功\n");

}





//计算模式串的next
void getNext(char * b){
    int len = strlen(b);
    next[0] = -1;
    int i =0 ,j =-1;
    for(i = 0;i<len;i++){
        if(next[i]==-1||b[i]==b[j]){
                next[i] = j;
                j++;
        }else{
            j = next[j];
        }
    }
}


//KMP计算
int KMP(char *a,char *b,int start){

    int len1 = strlen(a);
    int len2 = strlen(b);
    int i = start,j=0;
   while(i<len1&&j<len2){
        if(next[j]==-1||a[i]==b[j]){
            i++;
            j++;
        }else{
            j = next[j];
        }
        if(j==len2){
            return i-j;
        }
    }
    return -1;
}


//子串的查找
void substring(char *a,char *b,int start){
    getNext(b);
    int n = KMP(a,b,start);

    if(n==-1){
        printf("没有该字串\n");
        return ;
    }else{
        num++;
    }
    start = n+strlen(b) ;
    while(n!=-1&&start<strlen(a)){
        n = KMP(a,b,start);
        if(n!=-1){
            num++;
            start = n +strlen(b);
        }
    }
    printf("查找成功\n");
    printf("有%d个子串\n",num);
}


//输出模式串的next
void showNext(char *b){
    printf("\n该模式串的next值为:\n\n");
    for(int i =0 ;i<strlen(b);i++){
        printf("%d ",next[i]);
    }
    printf("\n");
}


//替换子串
void replace(char *a,char *b,char*c,int start){
    getNext(b);

    int n = KMP(a,b,start);

    if(n==-1){
        printf("没有该字串,不能进行替换\n");
        return ;
    }

   int i = 0,j=0;
   int len = strlen(c);

   while(i<n){
    d[j++] = a[i++];
   }
   strcat(d,c);
   j+=len;

    start = n+strlen(b) ;
    i = start;
    while(n!=-1&&start<strlen(a)){
        n = KMP(a,b,start);
        if(n!=-1){
            while(i<n)
            d[j++] = a[i++];

            strcat(d,c);
            j+=len;
            start = n +strlen(b);
            i = start;
        }
    }
    while(i<=strlen(a)){
        d[j++] = a[i++];
    }
    printf("\n替换前: %s\n",a);
    printf("替换后: %s\n\n",d);

}