编写算法strReplace(HString P, HString S),将当前串中首次出现的子串P替换成S。C语言

实现如下：

#include <stdio.h>
#include <string.h>

// 原串结构体
typedef struct HString {
    char *str; // 串指针
    int length; // 串长度
} HString;

// 初始化原串
void initString(HString *s, char *str) {
    int len = strlen(str);
    s->str = (char *)malloc(len + 1);
    strcpy(s->str, str);
    s->length = len;
}

// 子串结构体
typedef struct SubString {
    HString s; // 子串
    int pos; // 子串在原串中的位置
} SubString;

// 查找子串
int index(HString s, HString t) {
    int i = 0, j = 0;
    while (i < s.length && j < t.length) {
        if (s.str[i] == t.str[j]) {
            i++;
            j++;
        } else {
            i = i - j + 1;
            j = 0;
        }
    }
    if (j == t.length) {
        return i - t.length;
    } else {
        return -1;
    }
}

// 替换子串
HString strReplace(HString P, HString S, HString org) {
    // 查找子串
    int pos = index(org, P);
    if (pos == -1) { // 若子串不存在，返回原串
        return org;
    } else { 
        // 申请新串空间
        int len = org.length - P.length + S.length;
        HString newStr;
        newStr.str = (char *)malloc(len + 1);
        newStr.length = len;
        // 拷贝前半部分
        strncpy(newStr.str, org.str, pos);
        // 拷贝替换部分
        strncpy(newStr.str + pos, S.str, S.length);
        // 拷贝后半部分
        strncpy(newStr.str + pos + S.length, org.str + pos + P.length, org.length - pos - P.length);
        // 空串结尾
        newStr.str[len] = '\0';
        return newStr;
    }
}

int main() {
    HString org, P, S, newStr;
    initString(&org, "hello world, hello!");
    initString(&P, "hello");
    initString(&S, "hi");
    newStr = strReplace(P, S, org);
    printf("org = %s\n", org.str);
    printf("newStr = %s\n", newStr.str);
    return 0;
}