prefixsuffix：前綴和後綴的魔法

作為一個編程開發工程師，當涉及到字元串操作時，我們經常使用到前綴和後綴的技巧。本文將從多個方面詳細探討prefixsuffix的應用，包括它的定義、用法、複雜度以及代碼示例。

一、前綴和後綴的定義

在介紹prefixsuffix的用法之前，我們先來了解一下它的定義。前綴是指字元串的一部分，從開頭一直延伸到任何位置，包括原字元串本身。後綴則是指字元串的一部分，從任何位置開始，一直延伸到結尾，同樣包括原字元串本身。基於這個定義，prefixsuffix是指計算出字元串中每個位置的前綴和後綴。

例如，對於字元串”hello”，我們可以計算出它的每個位置的前綴和後綴如下：

前綴：h, he, hel, hell, hello
後綴：o, lo, llo, ello, hello

二、prefixsuffix的用法

prefixsuffix的一個重要用法是用來查找字元串中是否存在某個子串。假設我們要在字元串S中查找子串P，如果存在直接返回子串P在字元串S中第一次出現的位置，如果不存在則返回-1。使用prefixsuffix的演算法可以在O(N+M)的時間內計算出結果，其中N是字元串S的長度，M是字元串P的長度。

具體實現時，我們需要先計算S和P的前綴和後綴。然後我們從左到右遍歷字元串S，同時也從左到右遍歷字元串P，比較它們的對應字元是否相同。假設S中的第i個字元與P中的第j個字元不同，那麼我們就需要移動P的對齊位置，使得當前比較的字元是S中的下一個字元，即比較S的i+1和P的j。具體地，我們可以移動P的對齊位置，讓它指向最長公共前後綴的下一個位置。這個位置即S中從i開始往前的後綴和P的前綴的最長公共前後綴的下一個位置。如果沒有最長公共前後綴，我們就直接將P的對齊位置移到i的下一個位置。簡單來說，就是「匹配不上就跟進」。

三、prefixsuffix的複雜度

prefixsuffix演算法的時間複雜度為O(N+M)，其中N是字元串S的長度，M是字元串P的長度。空間複雜度為O(M)。

四、代碼示例

void prefix_suffix(const string& s, vector& pi) {
    int n = s.length();
    pi.resize(n);
    for (int i = 1; i  0 && s[i] != s[j]) {
            j = pi[j - 1];
        }
        if (s[i] == s[j]) {
            j++;
        }
        pi[i] = j;
    }
}

int prefix_suffix_match(const string& s, const string& p) {
    vector pi;
    prefix_suffix(p, pi);

    int n = s.length(), m = p.length();
    int j = 0;
    for (int i = 0; i  0 && s[i] != p[j]) {
            j = pi[j - 1];
        }
        if (s[i] == p[j]) {
            j++;
        }
        if (j == m) {
            return i - m + 1;
        }
    }

    return -1;
}

五、結語

本文介紹了prefixsuffix的定義、用法、複雜度以及代碼示例。其實，prefixsuffix還有很多其他的應用場景，比如KMP演算法、AC自動機等等，這些演算法都是基於prefixsuffix的思想發展而來。希望本文能對讀者加深對prefixsuffix的理解，也能對讀者在日常的編碼工作中有所幫助。