Ամենաերկար նախածանցը

Գևորգն ունի s տողը, որն իրենից ներկայացնում է անգլերեն փոքրատառերից կազմված հաջորդականություն։ Նա որոշել է ստանալ նոր տող իր ունեցած տողից հետևյալ կերպ. նա վերցնում է սկզբնական տողի որևէ տառեր և, հարաբերական հերթականությունը չփոխելով, գրում է իրար կողք։ Այլ կերպ ասած՝ եթե սկզբնական տողի տառերը նշանակենք -երով՝ , ապա Գևորգն ընտրում է որևէ k թիվ,  ինդեքսներ և ստանում նոր տող՝։ Այդպես, օրինակ, abbc տողից կարելի է ստանալ հետևյալ տողերը՝ a, b, c, ab, ac, bb, bc, abb, abc, bbc և abbc։ Նրա նպատակն է ստանալ այնպիսի նոր տող, որը հանդիսանա սկզբնական տողի նախածանց։ Բայց կա մի պայման. չպետք է վերցված բոլոր տառերը s-ի k երկարության նախածանցից լինեն, այսինքն` չպետք է տեղի ունենա հետևյալ պայմանը՝ )։