In-Place Replacement Replacement in C
Write a function
void inplace(char *str,
const char pattern,
const char* replacement,
size_t mlen)
Input:: a str
string ending in \0
. the input indicates that we need an inplace algorithm.
pattern
: letter.
replacement
: line.
mlen
: the size of the memory contains the string str
starts from the beginning of the memory and which mlen
must be greaterstrlen(str)
The end result is still being indicated str
.
Note that all occurrences of the pattern must be replaced.
For example,
helelo\0...........
Here "helelo" is the string to be replaced with '\0'
at the end. After '\0'
there are L more valid bytes. We want to replace "e" with "123".
The simple approach works like this, we go through str
when the pattern is matched, we wrap everything else with space to fill in the replacement string, and then we replace the pattern with the replacement.
If the original string is long n
and contains only e
, we need the shifts (n-1) + (n-2) + ... + 1
.
Is there an algorithm that scans a string with only one pass and constant memory cost?
source to share
I think two passes are the minimum. In the first pass, count the number of characters to be replaced. Given that count
and the length of the replacement string, you can calculate the length of the last string. (And you have to make sure it will fit into the buffer.)
In the second pass, you scan the string backward (starting at the last character), copying the characters to their final location. When you come across a search character, copy the replacement string to that location.
In your example, the increase in length would be 2. So you would
copy str[5] which is '\0' to str[7]
copy str[4] which is 'o' to str[6]
copy str[3] which is 'l' to str[5]
copy str[2] which is 'l' to str[4]
at str[1] you find the 'e' so str[3]='3' str[2]='2' str[1]='1'
At this point, the output index is the same as the input index, so you can break the loop.
As @chux pointed out in the comments, cases where the replacement string is either empty or has exactly one character can be handled with a single forward pass through the string. Therefore, the code must handle these cases separately.
source to share
One-time solution for the candidate.
For each character in str
, recurse. After recursion, do the replacement.
It regenerates heavily.
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
// return 0:success else 1:fail
static int inplace_help(char *dest, const char *src, int pattern,
const char* replacement, size_t rlen, size_t mlen) {
printf("'%p' '%s' %c\n", dest, src, pattern);
if (*src == pattern) {
if (rlen > mlen) return 1;
if (inplace_help(dest + rlen, src + 1, pattern, replacement, rlen,
mlen - rlen)) return 1;
memcpy(dest, replacement, rlen);
return 0;
}
if (mlen == 0) return 1;
int replace1 = *src;
if (*src) {
if (inplace_help(dest + 1, src + 1, pattern, replacement, rlen, mlen - 1)) {
return 1;
}
}
*dest = replace1;
return 0;
}
void inplace(char *str, const char pattern, const char* replacement,
size_t mlen) {
if (pattern == 0) return;
if (mlen == 0) return;
if (*replacement == 0) return; // Insure str does not shrink.
inplace_help(str, str, pattern, replacement, strlen(replacement), mlen - 1);
}
int main(void) {
char str[1000] = "eeeeec";
inplace(str, 'e', "1234", sizeof str);
printf("'%s'\n", str); // --> '12341234123412341234c'
return 0;
}
source to share
The following assumes that the memory allocated for the string was initialized by something at some point in time, since the C standard does not seem to allow access to uninitialized memory. In practice, it will work fine.
It performs exactly two scans, the first across the entire allocated space and moves the line to the right edge of the space. The second scan is done over the line itself, which goes back to the left margin while it performs replacements.
I changed the prototype to return 0 on success; -1 on failure. I also allow the pattern to be a string. (Maybe one character was intentional? Easy to change, anyway.) (As written, the template shouldn't have a length of 0. Check it out.)
int inplace(char *str,
const char* pattern,
const char* replacement,
size_t mlen) {
/* We don't know how long the string is, but we know that it ends
with a NUL byte, so every time we hit a NUL byte, we reset
the output pointer.
*/
char* left = str + mlen;
char* right = left;
while (left > str) {
if (!*--left) right = str + mlen;
*--right = *left;
}
/* Naive left-to-right scan. KMP or BM would be more efficient. */
size_t patlen = strlen(pattern);
size_t replen = strlen(replacement);
for (;;) {
if (0 == strncmp(pattern, right, patlen)) {
right += patlen;
if (right - left < replen) return -1;
memcpy(left, replacement, replen);
left += replen;
} else {
if (!(*left++ = *right++)) break;
}
}
return 0;
}
source to share