word shifts

[Gabriel Genellina]

En Sun, 04 May 2008 03:35:05 -0300, George Sakkis <george.sakkis at gmail.com> escribió:
> On May 4, 2:04 am, "Gabriel Genellina" <gagsl-... at yahoo.com.ar> wrote:
>> En Sun, 04 May 2008 02:17:07 -0300, dave <squareswallo... at invalid.com> escribió:
>>
>> > I made a function that takes a word list (one word per line, text file)
>> > and searches for all the words in the list that are 'shifts' of
>> > eachother.  'abc' shifted 1 is 'bcd'
>>
>> But I'd use a different algorithm. Instead of generating all posible shifts for a given word, I'd substract the newly read word from each previous words (here, "substract two words" means substract the character code for corresponding positions, modulo 26). Shifted words, when substracted, have the same number on all positions.
>
> A faster algorithm is to create a 'key' for each word, defined as the
> tuple of ord differences (modulo 26) of consecutive characters. E.g.
> the key of 'acf' is (2,3); 'c' is 2 positions after 'a' and 'f' 3
> positions after 'c'. Shifted words (and only these) have the same key.

Much better! I like it.

-- 
Gabriel Genellina