Re: Deleting substrings

Now, suppose the substring is a lil bigger..say of 5 characters or
even more.
What could be an efficient way in which it could be checked whether the
substring is present in the string or not. Preferably without using
extra memory..


ophidian wrote:
On Thu, 29 Jun 2006 06:12:53 -0700, goose wrote:

Chris Dollin wrote:
goose wrote:


<snipped>


1. We start at the beginning of the string.
abcxyghixy
^

2. We scan from that point for "xy" and if we don't find it
then we are done, if we find it then we are at the following point
in the string:
abcxyghixy
^

3. We copy the characters from the point immediately after
"xy" into the current position:
abcghixy
^

4. We repeat steps 2 and 3 until step 2 tells us that we are done.

Not as a criticism of your solution (I'm just piggybacking), but
I wonder what the OP intends to do with

abcxxyydef

After `delete A from B`, is it allowed for the result to contain A?

Er. Requirements error :-) ?


[If not, then we just need to restart the scan not from where we
left off, but from a "suitable distance" before then.]

<speculation>
Would probably be faster to keep it the same (start off where
we stopped) and wrap *that* into a loop which only ends when
no changes are made in the inner loop rather than repeatedly
starting from the beginning of the haystack[1] again (for
arbitrarily long needles[1] "suitable distance" would initially
mean starting from the beginning) each time we make a change.

<snip>

How about keeping a record of the first occurrence if the first character
of the substring in the host string? Then, if a substring is removed,
scanning is restarted from that position. If there is no record of an
occurrence of that character, or if we've just removed it as a result of
sub-string deletion, we resume where we left off. That should eliminate
redundant scans of the host string.

.

Relevant Pages

  • Re: How does this work?
    ... Let's say the string value is ... The value of the first argument is the substring that matched. ... the match extends as long as the delimiter characters don't match. ... So, as you can probably see now, it is actually a simple template engine ...
    (comp.lang.javascript)
  • Re: "Reversed" LCS problem
    ... have to worry so much about defining "substring" versus "subsequence," ... say "the letters in the string must be next to each other, ... >> has the lowest number of common characters from the other strings, ... > No whitespaces, no sequences, only substrings. ...
    (comp.programming)
  • Re: split a string
    ... >I have a string of N characters. ... >more ‘*' characters, which are the delimiter for the substring. ...
    (alt.comp.lang.learn.c-cpp)
  • Re: read text file
    ... 20 characters long and I need to look for the item at position 31. ... I get the following error "input string is in the incorrect format" and this ... >> I need to use SubString because I need to get only certain dataitems, ... > What Line is throwing the exception? ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: How to convert Infix notation to postfix notation
    ... If this is for an error message, why isn't it using stderr for its output? ... array of 15 characters, and you call this function with the limit 15 on ... Making sure that the only string I allocate and append to, ... because mulFactor in all versions must needs incorporate the functions ...
    (comp.lang.c)