Header <regex> su CMS

Aiuto
1

CMS si oppone all’uso dell’header <regex> e delle funzioni provenienti da esso? Lo chiedo perché ho provato a risolvere ois_html chiamando in soldoni %s/&amp;/&/g finché esiste la stringa &amp; e nonostante funzioni senza problemi in locale non prende nemmeno i casi d’esempio su CMS… di seguito il codice usato (s e r sono due std::string)

void unescape()
{
    int i;
    regex esc("&amp;");
    string sub("&");

    for (i = 0; i < N; i++) s.push_back(S[i]);

    while (regex_search(s, esc)) {
        r = regex_replace(s, esc, sub);
        s = r;
    }
}
2

Al momento viene usato per compilare le soluzioni sottoposte g++ 4.8 che supporta male regex perché l’implementazione era all’epoca a uno stadio molto '“beta”.
Per poter utilizzare in modo consistente tali funzionalità è necessaria almeno la versione 4.9.

1 Mi Piace
3

Capito! Che tu sappia alle nazionali sarà possibile usare <regex>?

4

Per quanto io ne sappia, quasi mai si dovrebbe usare una regexp per cercare un pattern in una stringa, principalmente perché spesso si tratta di versioni molto semplici di “ricerca regolare”.
Comunque, la tua soluzione è giusta, ma poco efficiente.

Prima di tutto, hai già una stringa S, perché ricopiarla tutta in s? Perché poi con dei push_back anziché usare il costruttore di copia? (quindi O(N) più overhead della push_back si spera poco influenti).
In secondo luogo, quando la regexp effettua una sostituzione, essa crea una stringa clone senza quel pattern (la sola copia richiede O(N) operazioni);

In terzo luogo, la regex conviene quando stai cercando pattern che sono più lunghi di un carattere. Una ricerca lineare del ‘&’ era più che sufficiente, e basta verificare se appena dopo ‘&’ c’è ‘amp;’

Questa l’idea che ho usato nel mio programma che risulta tra i più veloci nella classifica delle sottoposizioni (ok, perdonate la mia vanità)

// codice scritto in C, non C++
#include <string.h>
#include <stdio.h>

#define MAX 1000000

int main()
{
    char messaggio[MAX];
    char ris[MAX];
    int N, pos = 0;


    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    scanf("%d", &N);
    (void)getchar();
    fread(messaggio, N, sizeof(char), stdin);

    for(int i = 0; i < N;)
    {
        ris[pos++] = messaggio[i];

        if(messaggio[i++] == '&') {
            while(!strncmp(messaggio + i, "amp;", 4))
                i+=4;
        }
    }
    printf("%d\n", pos);
    fwrite(ris, pos, sizeof(char), stdout);

    return 0;
}

La complessità del mio programma è O(N) nel caso peggiore, il tuo O(N(4N + N)) = O(5N²) (se non ho sbagliato i conti, e escludendo la complessità intrinseca di regexp).

Morale: mai copiare una stringa a meno che non lo faccia poche volte.
Idem per i vettori in generale;

5

Avevo già risolto html in questo modo (non fosse che nell’ultimo task fa un bel segfault che mi fa prendere 70/100), questa conregex era solo una prova per testare nuove funzioni del linguaggio :stuck_out_tongue:

6

Ragionevolmente sì (Ubuntu 16.04 include già g++ 5), ma dubito ti sarà di aiuto :wink: