Iata sursa mea care are complexitate O(N + M):
#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";
}