My solution is under nickname "mogo" in the qualification round if you
want to have a look. The only thing that I save is a single dimension
array of length 19.
The solution to this problem is based dynamic programming and here's a
short explanation of the way it works:
The first thing that you have to notice is that if you know the number
of occurences of each substring 0..k from the key ("welcome to
codejam") in a string s1 then there's a simple (recurrent) formula to
compute the number of occurences for each substring 1..k in s1+c where
c is a single caracter. So you add once char and compute the new
values for it.
Here's an example for you to understand:
The substrings 0..k from the string "welcome to codejam" that I was
talking about are:
k=0 "w"
k=1 "we"
k=2 "wel"
k=3 "welc"
....
k=16 "welcome to codeja"
k=17 "welcome to codejam"
The recurrent formula is:
if(c == key[0]) //where key is the key string "welcome to codejam"
nr[0]++;
if(c == key[j])
nr[j]+=nr[j-1];
To explain the formula here's an example of how it works:
let s1 = "test w test el"
let c = 'l' //small L
we know that:
nr[0] = 1 // the number of 'w' letters in s1 (on position 5)
nr[1] = 2 // the number of "we" substrings in s1 (postitions 5, 8 and
5, 12)
nr[2] = 2 // the number of "wel" substrings in s1 (5, 8, 13 and 5, 12,
13)
nr[3] = ... = nr[17] = 0
Now if we add another 'l' to s1 then we'll get that
nr[0] = 1 // same number of w
nr[1] = 2 // same number of we
nr[2] = 4 // because key[2] = 'l' = c we know that for each substring
"we" that we were able to generate from s1 we will also be able to
generate a "wel" substring using letter c now.
After you understand the idea, implementation becomes very
straghtforward.
On Sep 9, 12:34 am, Misha Marchenko <[email protected]> wrote:
> Кажется у меня появилась идея как это можно сделать, нужно будет попробывать
>
> 9 сентября 2009 г. 10:33 пользователь romanr <[email protected]> написал:
>
>
>
> > По идее разбиваем строку на голову и хвост.
> > Так вот обрати внимание: часто приходятся решать задачу для той-же самой
> > головы и хвоста.
> > Вот этот результат и закешируй.
> > Можешь как кеш использовать двумерный массив с индексами в которых
> > разбивается на голову и хвост текст и искомая строка,
> > или хешируйся по конкатенации хвостов текста и искомой строки.
>
> > Misha Marchenko wrote:
>
> > Решал на жаве в лоб, без кеширования. Что к данной задаче будет
> > кешированием?
>
> > 8 сентября 2009 г. 21:49 пользователь romanr <[email protected]> написал:
>
> >> Решай "в лоб" с кешированием - это называется "динамическое
> >> программирование".
>
> >> Misha Marchenko wrote:
>
> >> Смотрел. Мне интереснее какой алгоритм был использован, какого его
> >> название? В том году я узнал, например, про венгерский алгоритм- Hide
> >> quoted text -
>
> - Show quoted text -
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"google-codejam" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/google-code?hl=en
-~----------~----~----~----~------~----~------~--~---
