Pagini: 1 [2]   În jos
  Imprimă  
Ajutor Subiect: Potrivire  (Citit de 9795 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #25 : Mai 12, 2012, 10:43:00 »

Iata sursa mea care are complexitate O(N + M):

Cod:
#include <fstream>
#include <string>
#include <vector>
using namespace std;

#define FORIT(it, v) for (typeof((v).begin()) it = (v).begin(); it != (v).end(); ++it)

ifstream fin("potrivire.in");
ofstream fout("potrivire.out");

const int MAX_N = 10005;

int n, m;
string text, pattern;
int prefix[MAX_N];

vector<string> tokenize(string &s) {
    vector<string> tokens;
    string token;

    FORIT(it, s)
        if (*it == '*') {
            if (!token.empty())
                tokens.push_back(token);
            token.clear();
        } else {
            token += *it;
        }
    if (!token.empty())
        tokens.push_back(token);

    return tokens;
}

void find_prefix(string &pattern) {
    m = pattern.size();

    int p = 0;
    prefix[1] = 0;

    for (int i = 2; i <= m; ++i) {
        while (p && pattern[p] != pattern[i - 1])
            p = prefix[p];
        if (pattern[p] == pattern[i - 1])
            ++p;
        prefix[i] = p;
    }
}

int main() {
    fin >> n >> m;
    fin >> text >> pattern;

    vector<string> tokens = tokenize(pattern);
   
    int idx = 0, left = -1, right = -1;
    for (size_t i = 0; i < tokens.size(); ++i) {
        find_prefix(tokens[i]);

        int p = 0;
        while (p != m) {
            if (idx == n) {
                fout << "-1\n";
                return 0;
            }

            while (p && tokens[i][p] != text[idx])
                p = prefix[p];
            if (tokens[i][p] == text[idx])
                ++p;
            ++idx;
        }

        if (i == 0) left = idx - m + 1;
        if (i + 1 == tokens.size()) right = idx;
    }

    fout << left << " " << right << "\n";
}
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
PlayLikeNeverB4
Nu mai tace
*****

Karma: 212
Deconectat Deconectat

Mesaje: 721



Vezi Profilul
« Răspunde #26 : Mai 12, 2012, 13:23:31 »

Ma lamureste cineva si pe mine care e faza cu O(30 * (N + M))? Nu inteleg care este logica. Parcurg o singura data atat A-ul cat si B-ul. In sursa lui wefgef, de exemplu, find_prefix parcurge o portiune dintre stelute (deci per total M), iar idx parcurge sirul A (deci per total N).
Memorat
maritim
Vorbaret
****

Karma: 59
Deconectat Deconectat

Mesaje: 176



Vezi Profilul
« Răspunde #27 : Mai 12, 2012, 13:37:06 »

Depinde cum ai facut.

Din cate am inteles eu (sper sa nu ma insel), tu ai luat fiecare secventa ce se afla intre doua stelute si ai calculat cu KMP aparitiile acestei secvente in sirul A. Pentru fiecare secventa (numar de stelute + 1) faci KMP, ceea ce rezulta o complexitate O(Nr_stelute) * O(N+M) (a doua parte provine de la KMP).

Daca ai facut ca wefgef, atunci ai intradevar O(N+M), dar fara impartirea lui B in nr_stelute secvente.
Memorat
PlayLikeNeverB4
Nu mai tace
*****

Karma: 212
Deconectat Deconectat

Mesaje: 721



Vezi Profilul
« Răspunde #28 : Mai 12, 2012, 13:48:21 »

Am facut ca si wefgef, incepand cautarea in A dupa ultima pozitie gasita anterior. Mi se parea si mai complicat de implementat daca era sa caut de fiecare data in tot sirul A.
Memorat
maritim
Vorbaret
****

Karma: 59
Deconectat Deconectat

Mesaje: 176



Vezi Profilul
« Răspunde #29 : Mai 12, 2012, 13:55:02 »

Aici ai dreptate, solutia pe care am spus-o eu mi-a mancat zilele in timpul concursului, fiind necesar un cod de vreo 3 ori mai lung si cu ceva mai multe buguri posibile, dar in lipsa de altceva si cu o mica criza de timp s-a comportat mai mult decat decent Smile .
Memorat
Pagini: 1 [2]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines