请按注释的说明，用C语言实现以下函数的功能。 /*Name:replace Function:to replace substring s1 in string source with substring s2 Parameters:source,string supposed to hold substring s1,substring to be replaced s2,substring to replace substring s1 flag,case-sensitive flag, 1,case-sensitive 0,non-case-sensitive Return values: number of substrings haved been replaced*/ (Supplementary:To be not complicated,assume that the length of the string after replaced is not greater than 1024 bytes.)
inline bool isEqual(char a, char b, int flag) {
if (flag == 0)
return toupper(a) == toupper(b);
else
return a == b;
}
int* getNextArray(char* pattern, int flag) {
assert(pattern != NULL);
int len = strlen(pattern);
assert(len > 0);
int *next = (int*)malloc(sizeof(int) * len);
next[0] = -1;
for (int i = 0, j = -1; i < len - 1; i++) {
if (-1 == j || isEqual(pattern[i], pattern[j], flag)) {
i++; j++;
next[i] = j;
}
else {
j = next[j];
}
}
return next;
}
char* KMP(char* source, char* pattern, int flag) {
int lenSource = strlen(source);
int lenPattern = strlen(pattern);
assert(lenPattern > 0);
int* next = getNextArray(pattern, flag);
int i, j;
for (i = 0, j = 0; i < lenSource && j < lenPattern;) {
if (-1 == j || isEqual(source[i], pattern[j], flag)) {
i++; j++;
}
else {
j = next[j];
}
}
free(next);
if (j >= lenPattern)
return source + i - lenPattern;
else
return NULL;
}
void strncopy(char* dest, char* source, int n) {
for (int i = 0; i < n; i++) {
*dest++ = *source++;
}
}
int replace(char* source, char* s1, char* s2, int flag) {
int len1 = strlen(s1);
int len2 = strlen(s2);
int lenS = strlen(source);
char* newBegin = KMP(source, s1, flag);
if (newBegin == NULL)
return 0;
char newSource[1024];
char *pSource = source, *pNewSource = newSource;
int cnt = 0;
while (newBegin != NULL)
{
cnt++;
strncopy(pNewSource, pSource, newBegin - pSource);
pNewSource += newBegin - pSource;
pSource = newBegin + len1;
strncopy(pNewSource, s2, len2);
pNewSource += len2;
newBegin = KMP(pSource, s1, flag);
}
while (*pSource != '\0') {
*pNewSource++ = *pSource++;
}
*pNewSource = '\0';
pSource = source; pNewSource = newSource;
while (*pNewSource != '\0') {
*pSource++ = *pNewSource++;
}
return cnt;
}
