JOIN
Get Time
long_comps_intel  Problem Statement
Contest: Intel Multi-Threading Competition 3
Problem: StringSearch

Problem Statement

    The goal of this problem is to search a large string, S, (up to 2 million characters) for smaller strings, u, (up to 100K each). Given a string t=u[n], you would like to find an index, i such that:



is minimized, where dist(a,b) gives the distance between letters a and b (where the alphabet of letters characters is circular). You should return a int[], where element n of the return is the index you selected for string u[n].



In testing your code, S will be randomly generated using only the first letters uppercase letters, with random length skewed towards longer strings (see notes) and letters chosen uniformly in [4,26]. The strings being searched for will have lengths chosen at random, again skewed towards longer strings (see notes). Additionally, the search strings will not be random, but will be similar to some substring of S. More specifically, a substring of S will be selected. Then, each character will be incremented by some distance x (wrapping around) chosen from [-k..k] where k is a parameter chosen uniformly at random from 1 to 26 that is specific to the string being searched for (thus, each element of the u has its own k, and each character has its own x). The probability that some value x is chosen as the increment will be proportional to 1/(abs(x)+1).



Scoring will be based on two things. First, you must find a substring that minimizes the distance summation explained above for each string in the input. If you don't find the absolute minimum for each string, you will get a 0 for that case. Assuming that you do this properly, your score for a test case will be inversely proportional to your runtime (60/num_seconds). Your final score will be inversely proportional to the sum of your runtimes. For each case that you received a 0 on, 100 seconds will be added to this sum. Thus, if you complete two test cases correctly in 20 and 40 seconds, but fail a third case, your score would be inversely proportional to 160.



 

Definition

    
Class:StringSearch
Method:search
Parameters:String, String[], int
Returns:int[]
Method signature:int[] search(String S, String[] u, int letters)
(be sure your method is public)
    
 

Notes

-Let rand() return a real number chosen uniformly at random in [0..1). Then, the length of the string S will be selected as 2,000,000*(1-rand()*rand()). The length of the strings being searched for will be selected as 100,000*(1-rand()*rand()), with a lower bound of 1000 characters and an upper bound of half the length of S. If an element of u has length which is not in this range, it is adjusted to the nearest edge of this range (i.e. 900 is adjusted to 1000).
-The examples are generated in similar fashion, but some will be smaller to facilitate testing.
-If the alphabet has 5 characters, for example, then it contains A, B, C, D and E. The distance from A to E is 1.
-Each search string will be at most half as long as S.
-The memory limit is 1024MB.
-The thread limit is 32.
 

Constraints

-You will be given 60 seconds per test case.
-S will be up to 2 million characters.
-u will contain exactly 16 elements, up to 100K each.
 

Examples

0)
    
This test case uses 9 letters.
S has 100 characters. The table below shows the length and optimal distance for the elements of u. Note that k is the value of k used to generate the string.
      |  len  | k | dist
------+-------+---+-------
u[0]  | 39    | 3 | 88    
u[1]  | 14    | 6 | 38    
u[2]  | 5     | 5 | 4     
u[3]  | 7     | 24| 18    
u[4]  | 49    | 19| 245   
u[5]  | 24    | 11| 107   
u[6]  | 14    | 21| 33    
u[7]  | 35    | 9 | 158   
u[8]  | 13    | 23| 40    
u[9]  | 40    | 15| 177   
u[10] | 33    | 21| 130   
u[11] | 50    | 13| 235   
u[12] | 10    | 9 | 31    
u[13] | 4     | 14| 4     
u[14] | 3     | 18| 1     
u[15] | 5     | 20| 10    
S = AFBEBIFIEIHECHBGHCCIFHGGHGGGHACDGDBFEDBCFGAAAGCIHDBHGFEGIFDAHIEGBFHBIIEBFHIHGGIG ABADFBEIEAHFGIHBDGHA

u[0] = EEBIDGCHAIEBHGBHGFGFIGDBHHEAEFBAIAFCGAH

u[1] = AGEAHDHGDGFBCC

u[2] = ACAGC

u[3] = CGDCFIB

u[4] = CDDIADAIDGBDGAEGEGHHADFFHHACFHEEDGIEIFIBEGIEGHFEF

u[5] = BCCGFCBHCIACGBIFEICBDEAG

u[6] = HCGCCCGIIABGBH

u[7] = HCDFBHAAGDFFAFCBAFBEBHHICHBBCCGHBFH

u[8] = GHIDDBEHFBIAF

u[9] = GHIDHHAFBADCIIDFAHCHFGFBGACIICGIDCFFDDHD

u[10] = AAIEFDHBDDAAGEBFGEFIBABCIEDGIGEFI

u[11] = HGFFGCAEAAAHDCAIAAGGDCCABDFGHHHGBFBHCCGHCGHBFGGGGI

u[12] = FFGBCICFGF

u[13] = CCID

u[14] = ABI

u[15] = HBHCG

1)
    
This test case uses 14 letters.
S has 300 characters. The table below shows the length and optimal distance for the elements of u. Note that k is the value of k used to generate the string.
      |  len  | k | dist
------+-------+---+-------
u[0]  | 111   | 19| 1209  
u[1]  | 32    | 16| 275   
u[2]  | 103   | 3 | 254   
u[3]  | 65    | 4 | 357   
u[4]  | 62    | 4 | 210   
u[5]  | 83    | 19| 1031  
u[6]  | 65    | 1 | 35    
u[7]  | 107   | 13| 1036  
u[8]  | 88    | 5 | 622   
u[9]  | 50    | 13| 567   
u[10] | 43    | 7 | 374   
u[11] | 96    | 5 | 521   
u[12] | 14    | 25| 107   
u[13] | 60    | 2 | 101   
u[14] | 144   | 18| 1595  
u[15] | 36    | 21| 374   
S = JAKIEDFAGLMAEABLMEIDHEBJIJBFCGFDKGJCJDABJHALHBEFFDFCMJKDFNIBMJFLABAFLAACIJJCLHIG JAACICMMHMKHJFDCBNJFEDBDDLHEHHKIMKKCJLGIEJHGCJMKEIIBECEMLAACAIAJKLJMCFAKCCHAJFJN DCACAFALKKKBNCNFCGIJANGMFLEECHFBKLHGJFCNKFHGKINNDDAMNCLMBHEBCDNLMCKIEHBIBGHDJHFH JKDCDLDEIELAEEAHDABGLGGALDLFCIJCKMNEJMNGCMICCLBHGCMAMCELGNHN

u[0] = FEJNMFDMHENNHFIHBFMJFGHLKFMEJBFJBBJNHMDAEGDIFKGEGDJCIBKHGHNBJDJHAAIJNDLLKGNAKMMD BLGMFEGAADDJLJEEJNDKLAGGBEFAJCE

u[1] = BBADJCBNCNAADJDLKHILMDMCBGLIHBCL

u[2] = FGIHHFKDCBJHBLKDEIGECDMLJDFNICMGFMMBBGNAAEIIJCKGHGMBACFENKGBLJIDCAAMJFEBCADMJGJG IHNMHEJLDJEJFDBILJHHIMD

u[3] = KFMHHFFGAMAKEEMHKAGBBIBAMFIFILMABIMJGCJKDEJLBJCLHEDLNFKDMNBCAHFAE

u[4] = FNKKAMCNCLHDGHGNJHLBAFEEHGAKLLGJBDALCGGJLNNAFBBADLCBHDDCDLALBJ

u[5] = JJALDFNHIMLGJJFBCDCMCNCJMILGILGIHGKDBENNBCNJDJEBKEDHKGFHFFKJHFGJDBEKDLBNBHMCCHCG IIC

u[6] = AHNFLEDDHGCJKGHIFCAJFIGKHMACEBMACLLBIEBDDNLNBJIEGBIAFHDKHFHJLECEL

u[7] = EMLDEDBELGFFDHIBEFEIFNCJEMHKFKDNGJIGIAAIGNDHAIKDGCDMJLBKJGMNJDKADAILDADIMIFBMHND NFDIFABMLMIMFGLMJIGKGCMCELE

u[8] = CHNFDCKHLDEGBIMDEBBINNEADIANLMALBCEDBIHEKDDCEDGELCJFFJNLMHCJDDGHMABDMEDAAILHGNKE LFAIAHKL

u[9] = HAGFECMDKKMLKKMIMBJBLCMJGDJFHMBCNIELHCGLDNHJICKEDA

u[10] = CJNCILBKHFHMKADIMJDMHHDCNELCEHEEAEECNDABKLF

u[11] = EBHJHIMKHBKLHGDIHDDKBKJIJACCGKMLLAKNBAFAJMCFMKNAICJAFMFDAAEDJMKJKBCDAENGJJMNHNFJ JIBLECKJKLJEFEKD

u[12] = FGFJDICECFIHAK

u[13] = BHAGEDKHJBJDMNJFBNHCFDDFDDNJKEEMKDNJFLMNNDLBMCIJHELHJGJMNEKD

u[14] = KMJJNGMGDLNNEFHCLJNBIHHACGADBFHJGHBGCJFMDKEJDANENBKMNFCIAFGENLAJEBHBGNCBIHDCKCDH AAGIDLACLEFEKHLEKNLGBNKCCFKLBGFIDMKEHFIIALHDIMGGIFBMFBDCKCCEJGGH

u[15] = LLGKAHNKAKNMDKGIBDNDHCHAADMBKCGBFDNK

2)
    
This test case uses 22 letters.
S has 500 characters. The table below shows the length and optimal distance for the elements of u. Note that k is the value of k used to generate the string.
      |  len  | k | dist
------+-------+---+-------
u[0]  | 93    | 20| 2318  
u[1]  | 175   | 25| 4808  
u[2]  | 106   | 19| 2488  
u[3]  | 192   | 3 | 561   
u[4]  | 72    | 18| 1893  
u[5]  | 54    | 22| 1348  
u[6]  | 61    | 1 | 29    
u[7]  | 91    | 10| 1180  
u[8]  | 216   | 11| 5308  
u[9]  | 18    | 20| 316   
u[10] | 166   | 9 | 2367  
u[11] | 107   | 8 | 1427  
u[12] | 153   | 4 | 624   
u[13] | 148   | 20| 3817  
u[14] | 71    | 25| 2034  
u[15] | 43    | 14| 739   
S = HNNQCPFQDGPVRLLOKNBJLCKANVOMEOFIPRFHTQNTBHTDDJBNPUMVJSLMSQRNGNBOAUFCDQPOVQFQCIGP PESVQVVHASVCAPQDAOJKQAUJBHNTEFNTDJLNKNAPTLRCVFVFKVQIRVJUJURNPJBJLGGTUNLGMOROJSNH HCEJLKFJGQHGJRSFPBAUDQDJVFNHEDLSLVORUJQSQLROKRKBUKNTTVFBMERAFNSJUQSTODLITVFTILAP PCSGNECEBFFCJELSUAOQQPEVOFFSEHQKCTKNQKLJBNOKNFAAIDALFDKDALFQDAEIBDDQIOVUBUJKNVAL LSKHVSVMRTBLHKGFHRHQBAJMNAARVOADBHAIRTEKRIVVGBGVSFSQGLCTUCCMIRRESEIPSQLQLKGCIKNE KLQAEUJEGOORRNPGRUCFCEOKJTRVBEFSEKSCVFPUJIKJAEHCUGGPLQISTGGFBTOMFKNNMNPJGLTODONC RVPOOIVOARMCVOJOPRTB

u[0] = BJMEVCPVUGASCLQBVJQSKJSHGSKJIBSKBPUJSBKFKFGBHGHBJBETRNMITKLGGPVJGDQOTOIFTNPNDHJU EMIPPHILTMOTK

u[1] = EPGMHKBMALRIALDTIBVLDGONIUGJVUUJAQIBGGLESOMUTPMCBJNRQJKMHFMNKLERBGUUAFVIATQLTDJU JSAMPGNNGEDPVBIMAPCOGNMSALMJUQDFGNSGOCTHFBDSDPCKVEUPKHILRBOJUDVOJVKLCMOFKKFPQCBV LERBUNQTVPJIPES

u[2] = IUODOMSEJNJBEJTVNQBHPGUVUSATNVGLSLHMOMONDMVOIHRARIULIVBIGUGDMVOLQLGOHCVSCGNLHERR RVQGDQAFMKDHJQJEBKGURCRGVF

u[3] = IBMCKTVAOOORBVNDCQEHSJCRJOQJLHCOMKMDACJEBLGCKDVMHRDVEJCBBPFPVTUVLMQAALKTKGSUUMPA VOJKIHGRINDVHMOCDOVQCFCKTJUSBKPHSBHBJSUDTRGIEATEEMGSRDRFLPVQOPKHGDHMNFKKQBFULEHM NSRQMEPTDHAGMKKUSVDHEQCKPVBHNAHH

u[4] = QAGVHNMTLHRUUMDOFGEGQKGGGTMKIKPASINKHJFFJHILPBBPTVJDBPCUNDVDAJVLBACLFNTT

u[5] = VAITBNIBNHFGCIJBALAPFMIFMJJCDITKQVRVKMPMUVMJQKHNIHOOEV

u[6] = CVKEQDBEICDDQHNVVCTIKNAALLTLHVRVMRUBKHLFFHRHRBAIMNABSAPVEAHAI

u[7] = ITRGMIDVDBFDUFCPFIERVDFJRVRVPVKUSRLRLCGCIKOUJOCVDDIEGMTRNRDNTUBFAEUKJAVUBEETEJBR VGPTNBIPAFH

u[8] = DOLKVPCRBNTQLRAERAAVDMVSCFTBFNOFNBJAQCUPDRVCQFSHGASRKFCGBUFBJFSPVISALLOQEATOMFHT NQLSTGBJKSIBLEJPIJKHDHNVJPKHAVQFBDHJRCQIOVUMQLMJVJQHDKRADARUUHQBVBSQRFUUKGMSHAPQ KKDVELPPTGMSEUVUALINKDPCLFDBCDEKORHSUEKHRSOLHCCIJTFKLRKU

u[9] = OIQVUVJNBTFTPUTARL

u[10] = FCVMQUNDPIUGLGHMSSRVVVOECEAEBRDVUUVSTRAPFBNMMSRHQKATMNRIKKBNOENEUAIVDLGDSDVICUBA BIULDKNPSTUUJSNTALMSKCUJVPTKTSJCHHVNFRQAJLKVRQTNTBEABMBTJQNJCVJDGACAORFIDEDCUQGV AJUEGK

u[11] = DNAVNBHULSUKBLCSPFBMGUBKUUEGGEHRNMUIELEURLPQQDVNFIQIDPKTTMNORLIUJOJPDCBISFFBSKCA OGSCUHIUDEJOOGBBDKGOOAGNSEB

u[12] = OQSPHARFGSCJQJETIOPJLMBROKQFVCJFCLBDOCAJEREBEJCDEQJPVCDAMLLRUNLRJHVRVMVUDLLKJFGO IRUCGLJABOUPVFAHAJQSHJRLSVKCKUSGANGHCTRBGMEVSERFJTRPIULNCBLOJEIMPCHTJFFMN

u[13] = LFMNVJJRPDRDNHQCSKJABGPUCJVVFBGANTLJKUSLLQJGJGSJEGAKOOHCTVGDGCEBOVAJUCGQAUAGMHNV FEFHUUCAPESQFEEGOAIRAQVAILLNELMRVBUPEEGBTNPPHOQFSCGRKJPULNCFTHBMTRJP

u[14] = VPOFRGTNIKBGGEMBERRHGKMVMLOJPVLEANBBIUQSPJHSRINGHBOCDBSLMHHRUCPDSEKRHFN

u[15] = AHRPUBRGRDVVHLLIGGQUNQTBUHKEFFIHQTVMPCEESTO

3)
    
This test case uses 4 letters.
S has 700 characters. The table below shows the length and optimal distance for the elements of u. Note that k is the value of k used to generate the string.
      |  len  | k | dist
------+-------+---+-------
u[0]  | 265   | 10| 321   
u[1]  | 45    | 9 | 41    
u[2]  | 105   | 11| 112   
u[3]  | 50    | 14| 41    
u[4]  | 335   | 17| 428   
u[5]  | 13    | 23| 6     
u[6]  | 12    | 1 | 5     
u[7]  | 163   | 6 | 182   
u[8]  | 289   | 25| 369   
u[9]  | 280   | 23| 359   
u[10] | 275   | 14| 351   
u[11] | 102   | 22| 111   
u[12] | 305   | 12| 385   
u[13] | 51    | 4 | 36    
u[14] | 62    | 13| 55    
u[15] | 224   | 2 | 272   
S = BCABDACADDBBACADCCABBCABCBDAABABDBABBCDBBDACACBBBBADDBCDACCCAADDDDCBACBABDADBCCC CACBBDDBCCBDCBADDDCABAADDABBBCCBBABDCDBBACDCABBADADDBCADCDCBDAADCCBABDAADDDABABD CABBCCABDCCDDABCCADDADDAACCCADBCBAADBDCBADBCBBABDBDBABCADCCDBACCCCBACAAADBDDDDCD DCACCCBDDCAACABCCDBACCCBCACBDCACCBAACAACCABCACBACCBCDDADCCDBBACCBBDACDCBCBACADCB ACCDAAACBDDBCACBBCBCDAADBACDBBDBAADCCCDDCCBADCDDBAAABDDBDDCAABBCBDCDDDDBACBDDBDB ADDDCDCABADDADBAADADACDBDDCBBADAACBCCAAABDADCBDAABBDBAADDBCAABDCDBBAADBCBDCDDACD ACDDDBADDDBADBACBCAABACDDCDDBBBCDBBCCADCCBABCDCCBACCCADACDDBCADABCCDBDBAACCCBDCD DCBCBBACABCCABBACDDBCCACCDCCDDABBDACADBBBBCBBBDCAAABCAACACCDCAABCAAAAAACBCDABADA CABDDCBCAAAACCBCDBCBCDBCBCDACABDADDBAAADAAABCCADACBABCDCDCAB

u[0] = CCCBBDCADDDDCCCCCADDADDBBDCCCBACAABBCBDABACACAAAAADCBDAABABBBBADBBADCDDDCDCDBDCB ABCBBADAACBAABCDBBDBDDACADADBBBADDCACBACBCBDACDBBBACBDBCDDBDBBACBADDCBDBBBDCDACB ABBADDDBBDAABBABCADBCABBBBBCABDDBDDABBDCCCCADABCCACBBCADDDCBDDCBCAADBBDAACDDDDDC CDACBBACDDAAACBDBCABACCBA

u[1] = BBBABCAAACDDBBBDCDDAACACCCADCADABCACDBCABBBDC

u[2] = BDCABBABCACBCCDDAACCBCDDABAACDDCCBCCABAADACBACAADABDDBABDCBBDDADADDCCDDACCBCDDDD BBDBADAABBDBAADBBDCABBAAA

u[3] = AABDDCBACBBCCABDABCADADCADCABCABDCCDCBADDDBBBDDABB

u[4] = DADADBADDBABABBACDCBCCCCDCDBCDDBCBBBBDBADDAADABAAACCDBDCDBCDCACABDDABADACDAABACB DDABCBACDCCACABDDCBAACCCDAADBDDCBABABABBDDABBACACBCACBACBDAAAAACBAACDCCABCBCBDDB DCBCABBBCCDCBABDBDDABBADDDABDBADBDCDCDAACCBADCBBADDDDBACBDDABABCBBCDAADABCBADAAC ACCCBCADBDBBDBBDCDCCADCBDCBABBDBCBDBCCABACCDCBDABABDBBADDDCBCABABABBCBDBBCBCBBAD ADDDAACCABBDBBD

u[5] = AACADCDCDCBDC

u[6] = CBDDDAAACCBC

u[7] = DDCACBDACCBCABBDACAABABCCABDBCDBCCAACDCBDDDDCDBDCCACCCABDDBCDDCADDADDDBDCADDCBBA DDBDCCBCBDABDACACCACDAAACBAAACCCDAABBACACABDBDABCABBBABBBCBCDCADCDCADCDCABDACBBD BBC

u[8] = BBDCDCADCAABAABBBABAADBDCACBBBDBACDABDCCBBDADADCBCCDBDCADBBBDBBCBCCABBADACCADCAB CABADBBCACCBBDBABBDCCDDDBCDDCCDBBBCAACBBDBBCBAADCDABABDBADCDCCCDCBCDBBCBDCCCACBB CCDCBAABABABDCDCAACDABBBCACDCBDCADCDABADABAAADCDCDBDCDACDDACDBCDDCCBAADCDDADDACC CCDADADDACACBDCDBCBACCDADDBBACACACBADDBDDABBDBABA

u[9] = DACBBABCDBBBCABAACCABCCBADCCABCACCBDCDBBDDCABADBDDAACDAAADABCBACCDBCCDCADDBBDCDB CDDBBDBBBBBCDDCABDBACCBCBDCDDBDBBBCCBABAAADDDABBBDDACCCDBCDCBAABCBBAACADABDABDAA ABADADDDBCCCABABCDBADDABBAADBBDBCBACCACCDCDBCBCACBBBCAACBABCCBBBBBABAAADBACDCDCC CACDADACADDABBAADABBCDADCADCACCCBDCCBDBD

u[10] = ABABAACDDCCCDCBBBCCBDAAAAACCADBAADCCDDBBADBCACBABDBCCBCBCCACDDBDBDBABBBBABCDACDC BDBCABDCABBDCDDADBBDDACCCACAADAACCCCDCBCADDDADDAACDBBCCBCCBCDBDDBCBDCAAABAAACADB BBCDBCAABABCBACBAACDCDCABAABDCCBACABBDABCBBCABCADDCACCBAAADBBDDDCDADCCADDCABBCDD DCCCBCBDDADDAAABCAAADADACCCBCCDDDBD

u[11] = AAABACBCBBCBDACABBCDCBBADABACACAAAADBBDADCAAABBBCDDBDCDABCBBCBBCCCCABBBDADABBABB DCCADDDCDCAABACADBAADC

u[12] = DCDADCBCDBACABDDAABBCCDCDDDBADAACCDBDDCCDDCCDBDAABBCADCCAAACDABDDBDCBBCDACCCABBD CDCACABACADDCBBBDADBBBBCACADBADDABCABDCDCDDDCDDCDBCBABBBBCBACBABDCDCAABCDDADAAAC DBDACADABCBCBDABAACCCDCAABABBDAAABABCBABDDACADBAABADAADDDBDDBADACCADCBDBAAADDAAC DBBAACBACBABACDBBBABDDCABADBDDBABDCCADBCACCCDCCADBCBBDDDBCACBCDCB

u[13] = CBACAADCABACDDADACCBAACACCBCDDDDABCDADDDBBAACCCBABD

u[14] = DBDBCBABCBABBDABDDBDDCBBACBDCAAAACDDBDDDDBDAABCCAAAADCDDDBCBCA

u[15] = DCACDDADBCCBACCACDAABBAACBDBADAABCBCADACDADCBCADDCDCCABBAABCBAAAABDABAABADADADAC DBCCDBBADADDCBCDDBABDADCDCCDACBAACABAACADABACDAADCCCACBBABCDDBCACCACCBCCDBBADBDC DBDCBBBADBCCCBDBDCCBBBAABDACCDDDAACDBCAAADCDDBCBAABAAAABDCBADBCC

4)
    
This test case uses 17 letters.
S has 1694112 characters. The table below shows the length and optimal distance for the elements of u. Note that k is the value of k used to generate the string.
      |  len  | k | dist
------+-------+---+-------
u[0]  | 63658 | 23| 997427
u[1]  | 98108 | 7 | 997172
u[2]  | 76622 | 12| 1306259
u[3]  | 91397 | 10| 1475706
u[4]  | 98489 | 22| 1534440
u[5]  | 39783 | 17| 639721
u[6]  | 82851 | 15| 1375691
u[7]  | 34364 | 16| 560449
u[8]  | 94042 | 8 | 1210716
u[9]  | 79640 | 14| 1349370
u[10] | 85072 | 21| 1304480
u[11] | 52817 | 18| 824043
u[12] | 90070 | 9 | 1344843
u[13] | 70683 | 21| 1083909
u[14] | 84601 | 25| 1414050
u[15] | 91476 | 4 | 372834
5)
    
This test case uses 5 letters.
S has 1973738 characters. The table below shows the length and optimal distance for the elements of u. Note that k is the value of k used to generate the string.
      |  len  | k | dist
------+-------+---+-------
u[0]  | 97815 | 23| 176285
u[1]  | 86642 | 21| 150293
u[2]  | 43234 | 22| 76633 
u[3]  | 44206 | 3 | 78767 
u[4]  | 75954 | 22| 134220
u[5]  | 50988 | 11| 83871 
u[6]  | 67809 | 7 | 112828
u[7]  | 86617 | 24| 155364
u[8]  | 99535 | 21| 172971
u[9]  | 52969 | 25| 93653 
u[10] | 77606 | 19| 137782
u[11] | 80626 | 23| 144772
u[12] | 56200 | 19| 99971 
u[13] | 60832 | 5 | 94313 
u[14] | 76158 | 14| 133813
u[15] | 86347 | 24| 154111
6)
    
This test case uses 26 letters.
S has 1986467 characters. The table below shows the length and optimal distance for the elements of u. Note that k is the value of k used to generate the string.
      |  len  | k | dist
------+-------+---+-------
u[0]  | 87709 | 6 | 695862
u[1]  | 92671 | 8 | 1190435
u[2]  | 76870 | 7 | 784885
u[3]  | 16125 | 21| 595951
u[4]  | 92585 | 4 | 377764
u[5]  | 85611 | 12| 2189769
u[6]  | 56086 | 2 | 76591 
u[7]  | 90952 | 21| 3324870
u[8]  | 85710 | 6 | 684427
u[9]  | 26554 | 24| 934856
u[10] | 89535 | 15| 3031706
u[11] | 73553 | 26| 2564627
u[12] | 99869 | 14| 3169907
u[13] | 22112 | 5 | 129705
u[14] | 36249 | 18| 1333492
u[15] | 38519 | 13| 1131079
7)
    
This test case uses 8 letters.
S has 1338285 characters. The table below shows the length and optimal distance for the elements of u. Note that k is the value of k used to generate the string.
      |  len  | k | dist
------+-------+---+-------
u[0]  | 97613 | 11| 402347
u[1]  | 44950 | 3 | 115586
u[2]  | 78948 | 9 | 315209
u[3]  | 66942 | 4 | 273133
u[4]  | 99639 | 24| 448403
u[5]  | 82223 | 17| 355301
u[6]  | 62894 | 18| 272202
u[7]  | 27372 | 16| 120202
u[8]  | 68496 | 13| 310913
u[9]  | 99444 | 11| 411339
u[10] | 96263 | 23| 440482
u[11] | 94240 | 16| 415317
u[12] | 33664 | 9 | 132129
u[13] | 10301 | 10| 40497 
u[14] | 97394 | 22| 450635
u[15] | 96678 | 5 | 436011

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.