Título: Substituição de strings
Linguagem: C/C++
S.O.: DOS/Windows
Autor(es): Wenderson Teixeira

Substituição de strings

Quando se trabalha com textos, é muito comum precisar-se substituir um trecho de uma string por outra, no entanto a biblioteca do padrão ANSI C não nos dá este recurso, você nunca se perguntou porque? Pois bem, vou tentar lhe explicar em poucas palavras, caso você ainda não tenha descoberto.
Em primeiro lugar, quando se utiliza strings alocadas estaticamente, o espaço reservado para armazenar essas strings é limitado, por isso não se pode, por exemplo, escrever além desse espaço, que é reservado durante a compilação, se você quebrar essa regra, você poderá estar escrevendo em um espaço reservado para outras variáveis do seu programa. Agora, quando se utiliza strings alocadas dinamicamente, tem se que tomar o cuidado de não exceder o espaço que foi alocado sem realocar mais espaço, pois nem sempre a área que você está tentando escrever pertence ao seu programa.
Tendo isso em mente eu implementei as rotinas Replace e OptimizedReplace, que realizam esta tarefa sempre tendo o cuidado de não invadir áreas de memória que não lhes pertencem.
Observe que Replace sempre aloca uma nova cópia da string quando faz uma substituição, isso a torna um pouco lenta, principalmente para string grandes e que tem muitas repetições, já OptimizedReplace se preocupa em só realizar uma nova alocação quando o trecho que está sendo substituido for menor que a string pela qual ele vá ser substituido, isso também faz com que, além de mais rápida, não fragmente tanto a memória, um efetio colateral do excesso de alocações. Ambas as rotinas retornam uma cópia da string de entrada com as devidas alterações realizadas, mantendo-se assim os parâmetros de entrada intactos, uma observação importante, é que o seu programa deve desalocar a string retornada por Replace e OptimizedReplace.
Com algumas poucas alterações pode se obter outras rotinas interssantes à partir destas duas, por exemplo, poderia-se modificá-las para que quando a string a ser substituida fosse encontrada, uma rotina fosse chamada e confirmasse com o usuário a substituição ou não dessa string, tornado-as interativas. Pode se também colocar testes para certificar que as alocações foram bem sucedidas, caso queira-se ter mais segunça quando se trabalhar com strings muito grandes.
O código fonte à seguir contém as duas rotinas e um programa de teste, as rotinas foram feitas utilizando-se basicamente de funções ANSI C, exceto por strdup, que apesar de não ser ANSI, é suportada pela maioria dos compiladores atuais, o programa de teste foi escrito em C++, mas utiliza apenas rotinas básicas de saída para o vídeo.

Replace.cpp

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <alloc.h>
#include <iostream.h>
#include <time.h>

/*--------------------------------------------------------------------
|   Substitue todas as ocorrencias de Str1 por Str2 em Src
|
|   Obs.:1) a string retornada por Replace nao e desalocada
|           automaticamente, e deve ser desalocada pelo
|           processo que o chamou
|        2) nao altera nenhum dos parametros de entrada
|        3) caso nao haja ocorrencias de Str1 em Src, sera retornada
|           uma copia de Src
|--------------------------------------------------------------------*/
char *Replace(const char *Src, const char *Str1, const char *Str2)
{
    // Cria uma copia de Src
    char *SrcCopy = strdup(Src);
    char *pTmp = SrcCopy;
    int sizeSrc = strlen(Src);
    int sizeStr1 = strlen(Str1);
    int sizeStr2 = strlen(Str2);
    do
    {
        // Acha o inicio de Str1 em Src
        pTmp = strstr(pTmp, Str1);
        if(pTmp)
        {
            int posStr1 = pTmp - SrcCopy;

            // Remove Str1 de Src
            int sizeRest = strlen(pTmp + sizeStr1);
            memmove(pTmp, pTmp + sizeStr1, sizeRest + 1);

            // Aloca a nova string com o novo tamanho
            sizeSrc = strlen(SrcCopy);
            SrcCopy = (char *)realloc(SrcCopy, sizeof(char) * (sizeSrc + sizeStr2 + 1));

            // Insere Str2 em Src
            memmove(SrcCopy + posStr1 + sizeStr2, SrcCopy + posStr1, sizeRest + 1);
            memmove(SrcCopy + posStr1, Str2, sizeStr2);
            pTmp = SrcCopy + posStr1 + sizeStr2;
        }
    } while(pTmp);

    return SrcCopy;
}


/*--------------------------------------------------------------------
|   Substitue todas as ocorrencias de Str1 por Str2 em Src
|
|   Obs.:1) a string retornada por OptimizedReplace nao e desalocada
|           automaticamente, e deve ser desalocada pelo
|           processo que o chamou
|        2) nao altera nenhum dos parametros de entrada
|        3) caso nao haja ocorrencias de Str1 em Src, sera retornada
|           uma copia de Src
|        4) Caso Str1 seja maior que Srt2, nao serao feitas alocacoes
|           ganhando-se em velocidade e menos fragmentacao de memoria
|--------------------------------------------------------------------*/
char *OptimizedReplace(char *Src, const char *Str1, const char *Str2)
{
    // Cria uma copia de Src
    char *SrcCopy = strdup(Src);
    char *pTmp = SrcCopy;
    int sizeStr1 = strlen(Str1);
    int sizeStr2 = strlen(Str2);
    int difSize = sizeStr2 - sizeStr1;  

    // Se Str2 for maior que Str1, execute o loop?
    if(difSize > 0)
    {
        do
        {
            // Acha o inicio de Str1 em Src
            pTmp = strstr(pTmp, Str1);
            if(pTmp)
            {
                int posStr1 = pTmp - SrcCopy;
                // Pega o tamanho de Src
                int sizeSrc = strlen(SrcCopy);
                // Pega o tamanho da string a partir do final de Str1 ate o final de Src
                int sizeRest = strlen(pTmp + sizeStr1);
                // Aloca memoria para comportar a nova string
                SrcCopy = (char *)realloc(SrcCopy, sizeof(char *) * (sizeSrc + difSize + 1));
                // Insere Str2 no lugar de Str1 ja deslocando o fim de Src corretamente
                pTmp = SrcCopy + posStr1;
                memmove(pTmp + sizeStr2, pTmp + sizeStr1, sizeRest + 1);
                memmove(pTmp, Str2, sizeStr2);
                pTmp += sizeStr2;
            }
        } while(pTmp);
    }
    // Otimizado para velocidade, sem executar nenhuma alocacao, ja que Str2 e menor que Str1
    else
    {
        do
        {
            // Acha o inicio de Str1 em Src
            pTmp = strstr(pTmp, Str1);
            if(pTmp)
            {
                // Pega o tamanho da string a partir do final de Str1 ate o final de Src
                int sizeRest = strlen(pTmp + sizeStr1);
                // Insere Str2 no lugar de Str1 ja deslocando o fim de Src corretamente
                memmove(pTmp + sizeStr2, pTmp + sizeStr1, sizeRest + 1);
                memmove(pTmp, Str2, sizeStr2);
            }
        } while(pTmp);
    }

    return SrcCopy;
}

int main(int ArgC, char *ArgV[])
{
    cout << "Teste de Rotina para Substituicao de String" << endl;
    cout << "    By Wenderson Teixeira" << endl;
    cout << "       Coppyright VIC - 1998. Todos os Direitos Reservados." << endl << endl;

    if(ArgC < 3)
    {
        cout << "Uso : Replace Source Str1 Str2" << endl;
        cout << "   Onde:" << endl;
        cout << "       Source - string contendo as ocurrencias de Str1" << endl;
        cout << "       Str1   - string a ser substituida" << endl;
        cout << "       Str2   - nova string" << endl << endl;
        return 1;
    }

    cout << "String original: " << ArgV[1] << endl;
    cout << "Substituir: " << ArgV[2] << endl;
    cout << "Por       : " << ArgV[3] << endl << endl;
    
    char *Str;

    Str = Replace(ArgV[1], ArgV[2], ArgV[3]);
    cout << "Utilizando Replace:" << endl;
    cout << "Nova String: " << Str << endl << endl;
    free(Str);

    Str = OptimizedReplace(ArgV[1], ArgV[2], ArgV[3]);
    cout << "Utilizando OptimizedReplace:" << endl;
    cout << "Nova String: " << Str << endl << endl;
    free(Str);

    return 0;
}