Potrivire

[•wefgef]

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";
}

[•PlayLikeNeverB4]

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).

[•maritim]

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.

[•PlayLikeNeverB4]

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.

[•maritim]

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 .