Проверка слова на маску.

[Null]

Задача такая(если это программирование перенесите тему туда).
Есть слово W из маленьких английских букв длинны m, и слово S из n больших английских букв.
Надо проверить можно ли получить W из S, заменив большие буквы словами из маленьких букв маленькими.
Одинаковые буквы должны заменяться одинаковыми словами.
Пример:
S=AA
слова aa,abab,cdccdc -представимы, ab,aba,acacac -нет.
S=ABA
Любое слово представимо если A - пустое.
S=ABBA
abbbab,cc -представимы, aba,abbaab,bbaababa -нет.

Лучше перебора по длинам заменяющих слов не придумывается. Как это сделать быстрее?
n<10..15 m<1000..5000

[Circiter]

Может быть попробовать что-нибудь вроде Z-функции?

[Joker_vD]

Это сильно смахивает на pattern-matching.

[Xaositect]

Я вот тут недавно читал Yacc is dead, мб тут тоже можно этот метод прикрутить?
Например, если мы хотим сматчить $ABCABC$ и прочитали первую букву $x$, то оставшееся должно сматчиться с $A'BCxA'BC$ либо (если $A$ пустое) с $B'CxB'C$, либо с $C'xC'$

[venco]

Xaositect в сообщении #398230 писал(а):

Например, если мы хотим сматчить $ABCABС$

Первая мысль - если хоть один символ в маске встречается только один раз, то эта маска подходит к любому слову.

[Xaositect]

Ой, у меня первая C правильная, а вторая почему-то русская.

[Null]

В вашем алгоритме на каждом шаге варианты множатся. $2^m$ - больно много.

А если завести массив размера $O(m^2 n^2)$ где $a[i,j,k,l]$- можно ли получить слово $W[i..j]$ из маски $S[k..l]$, только он очень большой и его считать долго.

[Xaositect]

Null в сообщении #398243 писал(а):

В вашем алгоритме на каждом шаге варианты множатся. $2^m$ - больно много.

В конкретно этом случае не множатся, если еще немного подумать. Там все мои три варианта на самом деле являются частными случаями первого. Но вполне возможно, что иногда будут, да.

[Null]

Xaositect в сообщении #398260 писал(а):

Null в сообщении #398243 писал(а):

В вашем алгоритме на каждом шаге варианты множатся. $2^m$ - больно много.

В конкретно этом случае не множатся, если еще немного подумать. Там все мои три варианта на самом деле являются частными случаями первого. Но вполне возможно, что иногда будут, да.

Это потому что ваша маска эквивалентна $AA$ или я чего-то не понял?

[Xaositect]

Null в сообщении #398264 писал(а):

Xaositect в сообщении #398260 писал(а):

Null в сообщении #398243 писал(а):

В вашем алгоритме на каждом шаге варианты множатся. $2^m$ - больно много.

В конкретно этом случае не множатся, если еще немного подумать. Там все мои три варианта на самом деле являются частными случаями первого. Но вполне возможно, что иногда будут, да.

Это потому что ваша маска эквивалентна $AA$ или я чего-то не понял?

Да, Вы правы, предложенный мной подход тут не сработает.

-- Вт янв 11, 2011 20:58:21 --

Null в сообщении #398243 писал(а):

А если завести массив размера $O(m^2 n^2)$ где $a[i,j,k,l]$- можно ли получить слово $W[i..j]$ из маски $S[k..l]$, только он очень большой и его считать долго.

Тут кстати все равно перебор нужен, так как если добавляется буква, которая уже была, то надо знать не только, что слово можно получить, но и как его можно получить.

[arseniiv]

(Оффтоп)

Joker_vD в сообщении #398202 писал(а):

Это сильно смахивает на pattern-matching.

Мне тоже так кажется. А там есть готовые решения?

[Joker_vD]

А давайте строить ДКА для строчки из больших букв, и скармливать ему строчку из маленьких?

[Xaositect]

Так не конечный же автомат будет.

[Joker_vD]

А почему не будет-то?

[Xaositect]

Joker_vD в сообщении #398324 писал(а):

А почему не будет-то?

Так ведь даже $\{ww|w\in A^*\}$ - нерегулярный язык, а дальше - больше. $\{www|w\in A^*\}$ даже не контекстно-свободный.