تکرار رشته‌ها

فرض کنید $‎w_n$,⋯,$w_1‎$ رشته‌هایی متمایز با حروف انگلیسی کوچک باشند که مجموع طول آن‌ها از ‎$Q$‎ تجاوز نمی‌کند. $‎W$ را نیز یک رشته انگلیسی دلخواه با طول $Q‎$ در نظر بگیرید.

عدد $‎a_i‎$ (که ‎ $i$=۱,⋯,$n$‎‎ است) را برابر تعداد ظاهرشدن رشته‎ $w_i$ ‎در $W$ تعریف می‌کنیم. به عنوان مثال، اگر ‎ $w_1=ab$، $‎w_2=aca$٬ ‎$w_3=bb$ و $‎W=abcabbb$‎ باشند، آنگاه $a_1 = 2$، ‎$a_2 = 0$‎‎ و ‎$a_3 = 2$‎ خواهد بود.

ثابت کنید:

‎$$min(a_1‎,‎a_2‎,‎⋯‎,‎a_n)\le \frac{2 \times Q \times \sqrt {Q}}n$$

پاسخ

تعریف: طول رشته $w_i$ برابر است با $len_{w_i}$ .
حرف $i$‌‌‌ام رشته $W$ نیز برابر است با $W_i$.

لم $1$: اگر مجموع $n$ عدد طبیعی متفاوت برابر با $S$ باشد، به دلیل متفاوت بودن اعداد، در حالتی $S$ مینیمم است که این مجموعه اعداد، همان اعداد $1,2,...,n$ باشند و در این حالت نیز $S$ برابر $ \frac { n \times (n+1) } 2 $ می‌شود. پس: $ \frac { n \times (n+1) } 2 \le S $.

اکنون عدد $b_i$ را اینگونه تعریف می‌کنیم. $b_i$ برابر است با تعداد دفعات ظاهر شدن رشته‌های $w_1$,..,$w_n$ در رشته $W$ به صورتی که اولین حرف از رشته ظاهر شده، حرف $i$ام رشته $W$ باشد. یعنی $b_i$ برابر است با تعداد $j$ هایی که: $ \overline{ { W_i{W_{i+1} }...W_{ {len_{w_j}} -1 } } } = w_j $ و نیز $B_i$ برابر با مجموعه این رشته‌ها (رشته‌هایی که در $b_i$ شمردیم) است . (به وضوح $ |B_i| = b_i $)

حال می‎توانیم بگوییم $ \sum{a_i} = \sum{b_i} $، زیرا با هر بار ظاهر شدن یکی از رشته‌ها در $W$، یکی از $a_i$ ها و یکی از $b_i$ ها هر کدام یک واحد افزایش میابند.

اکنون رشته‌های $B_i$ را در نظر بگیرید. طول هیچ دوتایی از این رشته‌ها نمی‎توانند با هم برابر باشند، زیرا اگر طول دو تا از این رشته‌ها، مانند $w_j$ و $w_k$ با هم برابر باشند (${len_{w_j}} = {len_{w_k}} $)، آنگاه $ w_j = \overline{ { {W_i}{W_{i+1}}...{W_{ {len_{w_j}} -1 } } } } = w_k $ و این با فرض متفاوت بودن رشته‌های $‎w_n$,⋯,$w_1‎$ تناقض دارد. پس طول رشته‌های موجود در $B_i$ ها اعدادی طبیعی و متفاوت‌اند و نیز طبق فرض سوال می‌دانیم، مجموع این طول‌ها کمتر از $Q$ است. پس اگر این مجموع برابر $S$ باشد، طبق لم $1$ و فرض سوال داریم: (تعداد اعضای $B_i$ = $b_i$)

$$ \frac { (b_i) \times (b_i+1) } 2 \le S \le Q $$
$$\Rightarrow { b_i \times (b_i +1) } \le {2 \times Q } $$
$$\Rightarrow { b_i \times b_i } \le { 2 \times Q } $$
$$\Rightarrow b_i \le { \sqrt {2 \times Q } } \le {2 \times {\sqrt Q } } $$

حال همه $b_i$‌ ها کوچکتر از ${2 \times {\sqrt Q } } $ هستند. در نتیجه داریم:
$$ \sum{b_i} \le {Q \times 2 \times {\sqrt Q} } $$ (چون تعداد $i$ های ممکن $Q$ تا است).

و نیز داشتیم که $ \Sigma{a_i} = \Sigma{b_i} $. در نتیجه:
$$ \sum{a_i} \le {Q \times 2 \times {\sqrt Q} } $$
$$\Rightarrow min(a_1‎,‎a_2‎,‎⋯‎,‎a_n) \times n \le \sum {a_i} \le {Q \times 2 \times {\sqrt Q} } $$
$$\Rightarrow min(a_1‎,‎a_2‎,‎⋯‎,‎a_n) \le \frac {Q \times 2 \times {\sqrt Q}}n $$