find and replace algorithm

[nitin1]

I was looking for the find and replace algorithm which editor softwares are using. for ex: notepad. when i search something and then when i replace it , how exactly it works. I am aware of rabin-karp and KMP algos. but i am wondering if they are most efficient ? and how do they replace it ? Seraching is okay, may be KMP can be applied, but replacing has some cases like when replaced words is of greater length and when it is of smaller length. Can you explain or give some link to it ? how will you shift whole text after that word in efficient way. thanks.

[Ancient Dragon]

I would use a temporary char array -- after you find the beginning of the string to be replaced copy the first part of the original string into the temp array, copy the replacement string into the temp buffer, then finally copy the remainder of the original string

Maybe a little more efficident way is to just copy the string that is past the part to be replaced into a temp buffer, for example if you have "The quick brown fox" and you want to change "brown" to "red", copy " fox" into a temp buffer. Next truncate the original string at the beginning of the string to be replaced -- in this example it will become "The quick ". Copy the replacement string into the end of the original string -- making it "The quick red". Finally, copy the contents of the temp buffer back to the end of the original -- "The quick red fox". Of course you should use strcat() to do the actual string contatinations.

[Klahr_R]

I did some tinkering with the example of Range.Find in MSDN and got this to work. "Knee" was used a lot in the file I was working.

    Private Sub FindAndReplace()
    Dim C As Range
    Dim FirstAddress As String
        With Worksheets(1).Range("a1:G40")
            Set C = .Find("Knee", LookIn:=xlValues)
            If C.Value <> Empty Then FirstAddress = C.Address
            If Not C Is Nothing Then
                Do
                    'Do what you need to do. I just printed to see that it worked
                    Debug.Print C.Address
                    Set C = .FindNext(C)
                Loop While Not C Is Nothing And C.Address <> FirstAddress
            End If
        End With
    End Sub

[Ancient Dragon]

That is VB.NET not C. Wrong forum.

[Klahr_R]

Ancient Dragon:
With appologies! I'm new to this and am likely to make mistakes.
This is not the thread I thought I was posting to and cannot find the one I thought I was posting to which included VB code that was similar to what I answered, and should have been from vb4/5/6 as that is my bookmark????
It was a nice tea with Alice, however.

[Ancient Dragon]

Nobody but me is allowed to make mistakes here! Anyone else is just banned :) (just kidding)

[nitin1]

@ancient dragon.. that one will use the too much space. because my text can be of miliions of characters of even more. so doing this is not good way. thanks for this , but can we think of anything more better ?

[Ancient Dragon]

Here is one suggestion from StackOverflow -- use sed shell program. Put the text in a file then run sed against it as shown in the example in that link.

[Adak]

Try Super sed. (for Windows command line, I believe).
http://sed.sourceforge.net/grabbag/ssed/

If you have a 2D char array, all the editing can be done in only a single row of text. This array only needs to have a few extra rows on each side of the visible text rows you see on-screen.

[Adak]

By "only a single row of text", I mean that conceptually, even a multi-line replacement, is handled just one line at a time.

Every system has a sweet spot for the number of rows to hold in the 2D char array, for fastest edits.

[rubberman]

You can create a sed script that will loop/process all the data in a file. I do this for processing script output into CSV format data. Here is an example from my bash script:

cat >$SEDFILE <<EOF
s/^/"/
# Convert space delimiters to ","
{
 : dospc
 s/ /","/
 t dospc
}
# Convert equal sign to "," to separate tag name from value.
{
 : doequ
 s/=/","/
 t doequ
}
s/$/"/
EOF

Each bracketed block is a "do while true" loop that will loop until the 's/...' condition no longer generates any matches. Normally sed will only match one element on a line. This allows you to match any number of similar elements on any number of lines. FWIW, this process works for input files of 100's of thousands of lines, and quite efficiently!