پرش به محتویات

تجزیه لیندون

تجزیه لیندون

ابتدا مفهوم تجزیه لیندون را تعریف می‌کنیم.

یک رشته ساده (یا کلمه لیندون) نامیده می‌شود، اگر اکیداً کوچکتر از تمام پسوندهای سره خود باشد. مثال‌هایی از رشته‌های ساده عبارتند از: $a$, $b$, $ab$, $aab$, $abb$, $ababb$, $abcd$. می‌توان نشان داد که یک رشته ساده است، اگر و تنها اگر اکیداً کوچکتر از تمام شیفت‌های دورانی غیربدیهی خود باشد.

حال، رشته $s$ را در نظر بگیرید. تجزیه لیندون برای رشته $s$، یک تجزیه به صورت $s = w_1 w_2 \dots w_k$ است، که در آن تمام رشته‌های $w_i$ ساده هستند و در ترتیب غیرصعودی $w_1 \ge w_2 \ge \dots \ge w_k$ قرار دارند.

می‌توان نشان داد که برای هر رشته‌ای چنین تجزیه‌ای وجود دارد و یکتاست.

الگوریتم دووال

الگوریتم دووال تجزیه لیندون را در زمان $O(n)$ و با استفاده از حافظه اضافی $O(1)$ می‌سازد.

ابتدا مفهوم دیگری را معرفی می‌کنیم: یک رشته $t$ پیش-ساده نامیده می‌شود، اگر به شکل $t = w w \dots w \overline{w}$ باشد، که در آن $w$ یک رشته ساده و $\overline{w}$ یک پیشوند از $w$ است (که می‌تواند تهی باشد). یک رشته ساده نیز پیش-ساده محسوب می‌شود.

الگوریتم دووال یک الگوریتم حریصانه است. در هر لحظه از اجرای الگوریتم، رشته $s$ عملاً به سه بخش $s = s_1 s_2 s_3$ تقسیم می‌شود. در این تقسیم‌بندی، تجزیه لیندون برای $s_1$ قبلاً پیدا و نهایی شده است، رشته $s_2$ یک رشته پیش-ساده است (و ما طول رشته ساده‌ی درون آن را می‌دانیم)، و $s_3$ بخش کاملاً دست‌نخورده رشته است. در هر تکرار، الگوریتم دووال اولین کاراکتر رشته $s_3$ را برداشته و سعی می‌کند آن را به انتهای رشته $s_2$ اضافه کند. اگر با این کار $s_2$ دیگر پیش-ساده نباشد، آنگاه تجزیه لیندون برای بخشی از $s_2$ مشخص می‌شود و این بخش به $s_1$ منتقل می‌گردد.

بیایید الگوریتم را با جزئیات بیشتری شرح دهیم. اشاره‌گر $i$ همیشه به ابتدای رشته $s_2$ اشاره می‌کند. حلقه بیرونی تا زمانی که $i < n$ باشد اجرا می‌شود. درون این حلقه از دو اشاره‌گر کمکی دیگر استفاده می‌کنیم: $j$ که به ابتدای $s_3$ اشاره می‌کند، و $k$ که به کاراکتری اشاره می‌کند که در حال مقایسه با آن هستیم. می‌خواهیم کاراکتر $s[j]$ را به رشته $s_2$ اضافه کنیم که این کار نیازمند مقایسه آن با کاراکتر $s[k]$ است. سه حالت مختلف ممکن است رخ دهد:

  • $s[j] = s[k]$: در این حالت، افزودن کاراکتر $s[j]$ به $s_2$ خاصیت پیش-سادگی آن را نقض نمی‌کند. بنابراین، به سادگی اشاره‌گرهای $j$ و $k$ را یک واحد افزایش می‌دهیم.
  • $s[j] > s[k]$: در این حالت، رشته $s_2 + s[j]$ ساده می‌شود. می‌توانیم $j$ را افزایش دهیم و $k$ را به ابتدای $s_2$ بازنشانی کنیم تا کاراکتر بعدی با ابتدای کلمه ساده جدید مقایسه شود.
  • $s[j] < s[k]$: در این حالت، رشته $s_2 + s[j]$ دیگر پیش-ساده نیست. بنابراین، بخش پیش-ساده $s_2$ را به تکرارهایی از یک کلمه ساده تجزیه می‌کنیم. طول این کلمه ساده $j - k$ است. این کلمات ساده به تجزیه نهایی اضافه می‌شوند و حلقه اصلی کار خود را با بخش باقی‌مانده از رشته $s$ ادامه می‌دهد.

پیاده‌سازی

در اینجا پیاده‌سازی الگوریتم دووال را ارائه می‌دهیم که تجزیه لیندون مورد نظر را برای رشته ورودی $s$ برمی‌گرداند.

vector<string> duval(string const& s) {
    int n = s.size();
    int i = 0;
    vector<string> factorization;
    while (i < n) {
        int j = i + 1, k = i;
        while (j < n && s[k] <= s[j]) {
            if (s[k] < s[j])
                k = i;
            else
                k++;
            j++;
        }
        while (i <= k) {
            factorization.push_back(s.substr(i, j - k));
            i += j - k;
        }
    }
    return factorization;
}

پیچیدگی

بیایید زمان اجرای این الگوریتم را تخمین بزنیم.

حلقه while بیرونی بیش از $n$ بار تکرار نمی‌شود، زیرا در پایان هر تکرار، مقدار $i$ افزایش می‌یابد. همچنین، حلقه while درونی دوم در مجموع در زمان $O(n)$ اجرا می‌شود، زیرا تنها تجزیه نهایی را به خروجی اضافه می‌کند.

بنابراین، تنها حلقه while درونی اول برای ما مهم است. این حلقه در بدترین حالت چند بار تکرار می‌شود؟ به راحتی می‌توان دید که کلمات ساده‌ای که در هر تکرار حلقه بیرونی شناسایی می‌کنیم، از بخش باقی‌مانده‌ای که به صورت اضافی مقایسه شده، طولانی‌تر هستند. بنابراین، مجموع طول این بخش‌های باقی‌مانده نیز کمتر از $n$ خواهد بود، که به این معنی است که ما در مجموع حداکثر $O(n)$ تکرار از حلقه while درونی اول انجام می‌دهیم. در واقع، تعداد کل مقایسه‌های کاراکتری از $4n - 3$ تجاوز نخواهد کرد.

یافتن کوچکترین شیفت دورانی

رشته $s$ را در نظر بگیرید. تجزیه لیندون را برای رشته $s + s$ (در زمان $O(n)$) می‌سازیم. ما به دنبال یک رشته ساده در این تجزیه خواهیم بود که از یک موقعیت کمتر از $n$ شروع شود (یعنی در نمونه اول $s$ آغاز شود) و در موقعیتی بزرگتر یا مساوی $n$ پایان یابد (یعنی در نمونه دوم $s$ تمام شود). ثابت شده است که موقعیت شروع این رشته ساده، ابتدای کوچکترین شیفت دورانی مورد نظر خواهد بود. این موضوع را می‌توان به راحتی با استفاده از تعریف تجزیه لیندون تأیید کرد.

ابتدای بلوک ساده را می‌توان به راحتی پیدا کرد؛ کافی است در ابتدای هر تکرار حلقه بیرونی، مقدار اشاره‌گر $i$ را که ابتدای رشته پیش-ساده فعلی را نشان می‌دهد، به خاطر بسپاریم.

بنابراین به پیاده‌سازی زیر می‌رسیم:

string min_cyclic_string(string s) {
    s += s;
    int n = s.size();
    int i = 0, ans = 0;
    while (i < n / 2) {
        ans = i;
        int j = i + 1, k = i;
        while (j < n && s[k] <= s[j]) {
            if (s[k] < s[j])
                k = i;
            else
                k++;
            j++;
        }
        while (i <= k)
            i += j - k;
    }
    return s.substr(ans, n / 2);
}

مسائل