Тема: Поиск подстрок в строке
Надо найти кол-во подстрок в строке (длина строки <= 50000)
Например:
text = 'ababa'
s = 'aba'
Ответом будет 4.
ababa
ababa
ababa
ababa
Re: Поиск подстрок в строке
Re: Поиск подстрок в строке
Разве это та же задача, что и http://e-maxx.ru/forum/viewtopic.php?id=38?
Здесь даны text и s, и надо посчитать количество вхождений s в text, причём в виде подпоследовательности?
Re: Поиск подстрок в строке
А линк на online-judge с этой задачей есть?
Re: Поиск подстрок в строке
Точно, невнимательно прочитал(
Re: Поиск подстрок в строке
Можно задачу более точно сформулировать? Пример и предложенное условие мало друг с другом согласованы...
Re: Поиск подстрок в строке
И еще это число может быть очень большим. Например, для строк {50000 а} и {25000 a}.... Определенно нужны уточнения.
8 2009-07-17 13:16:08 Отредактировано brainail (2009-07-17 21:48:58)
Re: Поиск подстрок в строке
даже если под это условие что подпоследовательности , то нужна длинка что никак вроде не успеет .
Ну а так для ограничений поменьше самое простое это динамика за O(NxM) 
Re: Поиск подстрок в строке
brainail пишет:
даже если под это условие что подпоследовательности , то нужна длинка что никак вроде не успеет .
Ну а так для ограничений поменьше самое простое это динамика за O(N^3)
Почему куб? Если без длинной арифметики(к примеру вывести ответ по какому-то модулю), то можно к примеру за O(NM).
f(i,j) это количество способов выбрать первые j символов строки s(в нужном порядке) в первых i символах text.
Тогда:
Если text(i)!=s(j), то f(i,j)=f(i-1,j)
Если text(i)==s(j), то f(i,j)=f(i-1,j)+f(i-1,j-1)
Re: Поиск подстрок в строке
Да уж 
Я просто не то умножил,переборщил !
Ну думаю можно наверняка за O(Nlog(N)) или O(Nsqrt(N)) .. Нужно поискать поглубже