字符串border系列学习笔记

一些定义和核心性质，对于算法理解有很大帮助,不妨考虑字符串全部为 $1base$

Border:若字符串S的 $prefix[i]=suffix[i]$ ，则称这个前缀或者这个后缀是一个border
周期：对于字符串S，存在整数P满足 $S[i]=S[i-P]$ $(p<i \le |S| )$ ,则P为字符串S的一个周期。这里的周期也常被称为循环覆盖。
循环节：若字符串S的周期P满足 $p\,|\, s.size()$ ,则P是S的一个循环节。

理解：周期用循环覆盖理解，就是长度P的周期拼接若干次以后，S一定作为这其中的子串出现。对于循环节来说，循环节拼接若干次以后，恰好能够得到S。

性质：

P是S的周期$\Leftrightarrow $$|S|-p$是S的border
border具有传递性：S的border的border也是S的border.因此得到推论：求S的所有border等价于求递归求所有S前缀的最大Border
周期定理：若p, q 均为串S 的周期，则(p, q) 也为S 的周期。
一个串的Border 数量是 $O(N)$ 个，但他们组成了 $O(logN)$ 个等差数列。

KMP板子

struct KMP {
    vector<int> nxt;
    string tt;
    int len;
    KMP() {}
    KMP(string t) {
        len = t.size();
        t = " " + t;
        tt = t;
        nxt.resize(len + 1);
        nxt[1] = nxt[0] = 0;
        init(tt);
    }

    void init(string t) {
        for (int i = 2; i <= len; i++) {
            nxt[i] = nxt[i - 1];
            while (nxt[i] && t[i] != t[nxt[i] + 1]) nxt[i] = nxt[nxt[i]];
            nxt[i] += (t[i] == t[nxt[i] + 1]);
        }
    }
    vector<int> getnxt() {
        return nxt;
    }
    vector<int> match(string &s, bool oneonly = 0) {
        int lens = s.size();
        s = " " + s;
        vector<int> stpos;
        int j = 0;
        for (int i = 1; i <= lens; i++) {
            while (j == len || (j && s[i] != tt[j + 1])) j = nxt[j];
            if (s[i] == tt[j + 1])
                j++;
            if (j == len)
                stpos.push_back(i - len + 1);
        }
        return stpos;
    }
}

https://www.luogu.com.cn/problem/UVA12467

题意：给定一个字符串s,求解最长子串T,满足R(T)是s的前缀。

Sol:考虑将s反转，插入分隔符评接到s后面，我们只需要在反转串范围内求解最长border。

void solve()
{
    string s;cin >> s;
    int n = s.size();
    string tmp = s;
    reverse(alls(tmp));
    s += "$" + tmp;
    KMP kmp(s);
    s = " " + s;
    int pos = 0;int mx = -1;
    for (int i = n + 2; i <= n + 2 + n - 1; i++)
    {
        if (mx < kmp.nxt[i])
        {
            mx = kmp.nxt[i];
            pos = i - mx + 1;
        }
    }
    tmp = s.substr(pos, mx);
    reverse(alls(tmp));
    cout << tmp << endl;
}

求字符串的最小循环覆盖:设长度为n，答案就是长度为 $n-nx[n]$ 的前缀

求字符串的最小循环节:检验n能不能被周期整除即可

1.https://www.luogu.com.cn/problem/UVA1328

对于给定字符串 S** 的每个前缀，我们想知道它是否为周期串（周期串定义为由若干最小循环节拼接而成的字符串），若是，输出前缀长度和循环节数量。

int cnt = 0;
void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    KMP kmp(s);
    cnt++;
    cout << "Test case #" << cnt << endl;
    for (int i = 2; i <= n; i++) {
        deb(i,kmp.nxt[i]);
        if (kmp.nxt[i]&&i % (i - kmp.nxt[i]) == 0)
            cout << i << " " << i / (i - kmp.nxt[i]) << endl;
    }
    cout << endl;
}

2.https://www.luogu.com.cn/problem/UVA10298

求一个字符串由多少个重复的子串连接而成

void solve()
{
    string s;
    while (cin >> s, s != ".")
    {
        KMP kmp(s);
        int n = s.size();
        s = " " + s;
        if (n % (n - kmp.nxt[n]) == 0)cout<<n/(n-kmp.nxt[n]<<endl;
      else cout<<n<<endl;
    }
}