// 朴素字符串匹配 — O(N * M)
vector<int> naive_search(string text, string pattern) {
    int n = text.size(), m = pattern.size();
    vector<int> result;
    for (int i = 0; i <= n - m; i++) {
        bool match = true;
        for (int j = 0; j < m; j++) {
            if (text[i + j] != pattern[j]) {
                match = false;
                break;
            }
        }
        if (match) result.push_back(i);
    }
    return result;
}

#include <bits/stdc++.h>
using namespace std;

// 构建前缀函数（KMP 的核心）
// 时间复杂度：O(N)
vector<int> prefix_function(const string& s) {
    int n = (int)s.length();
    vector<int> pi(n, 0);   // pi[0] = 0 是规定
    
    for (int i = 1; i < n; i++) {
        // j 从上一个 π 值开始尝试
        int j = pi[i - 1];
        
        // 失配时，利用已算出的 π 值回退（关键步骤！）
        while (j > 0 && s[i] != s[j])
            j = pi[j - 1];     // 跳到下一个候选长度
        
        // 匹配则长度加一
        if (s[i] == s[j])
            j++;
        
        pi[i] = j;
    }
    return pi;
}

// KMP 字符串匹配
// 返回 pattern 在 text 中所有匹配的起始下标（0-indexed）
// 时间复杂度：O(N + M)，N = len(text)，M = len(pattern)
vector<int> kmp_search(const string& text, const string& pattern) {
    if (pattern.empty()) return {};
    
    // 第一步：拼接，用不在字符集中的分隔符
    string combined = pattern + '#' + text;
    int m = pattern.size(), n = text.size();
    
    // 第二步：计算整体前缀函数
    vector<int> pi = prefix_function(combined);
    
    // 第三步：收集匹配位置
    vector<int> result;
    for (int i = m + 1; i <= m + n; i++) {
        if (pi[i] == m) {
            // i 在拼接串中的位置，换算回 text 中的起始位置
            result.push_back(i - 2 * m);
        }
    }
    return result;
}

int main() {
    string text    = "ababcabcabababd";
    string pattern = "abab";
    
    auto pos = kmp_search(text, pattern);
    cout << "模式串 \"" << pattern << "\" 出现在位置：";
    for (int p : pos) cout << p << " ";
    // 输出：0 8 10
    cout << endl;
    
    // 验证
    for (int p : pos) {
        cout << "  text[" << p << ".." << p+pattern.size()-1 << "] = "
             << text.substr(p, pattern.size()) << endl;
    }
    return 0;
}

text = "ababcabab", pattern = "abab"（长度4）

拼接串：  a b a b # a b a b c a b a b
π 值：    0 0 1 2 0 1 2 3 4 0 1 2 3 4
                         ↑           ↑
                       i=8          i=13
                    π[8]=4=m ✓    π[13]=4=m ✓

匹配位置（text 中 0-indexed）：
  i=8：  8 - 2*4 = 0  → text[0..3] = "abab" ✓
  i=13： 13 - 2*4 = 5 → text[5..8] = "abab" ✓

// 若字符串 s 能被前 k 个字符重复构成，则 k 是周期
// 最短周期 = n - π[n-1]
// 条件：n 能被 (n - π[n-1]) 整除

int min_period(const string& s) {
    int n = s.size();
    auto pi = prefix_function(s);
    int period = n - pi[n - 1];
    if (n % period == 0) return period;
    return n;  // 无法压缩，周期为 n
}

// 示例：
// "abcabc" → π[5]=3，period = 6-3 = 3，6%3=0 ✓，最短周期 3
// "abcab"  → π[4]=2，period = 5-2 = 3，5%3≠0，最短周期 5（整串）

// 统计模式串的每个前缀在整个串中出现的次数
vector<int> count_prefixes(const string& s) {
    int n = s.size();
    auto pi = prefix_function(s);
    vector<int> cnt(n + 1, 0);
    
    for (int i = 0; i < n; i++) cnt[pi[i]]++;    // 每个位置贡献
    for (int i = n - 1; i > 0; i--) cnt[pi[i-1]] += cnt[i]; // 传播
    for (int i = 0; i <= n; i++) cnt[i]++;        // 加上自身
    
    return cnt;  // cnt[k] = 长度为 k 的前缀在 s 中出现的次数
}

        根节点
       /      \
      c         b
     / \       / \
    a   ?     a   ?
   /|\        |
  t r n       r  t（"bat"和"bar"共享"ba"前缀）
             / \
            ★   ★
         "bar" "bat"

※ ★ 表示在该节点结尾的字符串存在（"end" 标记）

#include <bits/stdc++.h>
using namespace std;

// Trie 树（数组版，只支持小写字母）
const int MAXN = 500005;  // 最大节点数 = 总字符数

struct Trie {
    int ch[MAXN][26];  // ch[u][c] = 节点 u 的第 c 个子节点编号
    bool exist[MAXN];  // exist[u] = 以节点 u 结尾的字符串是否存在
    int cnt;           // 节点计数器（根节点为 0）
    
    Trie() : cnt(0) {
        memset(ch[0], 0, sizeof(ch[0]));  // 初始化根节点
        exist[0] = false;
    }
    
    // 插入字符串
    // 时间复杂度：O(|s|)
    void insert(const string& s) {
        int p = 0;  // 从根节点开始
        for (char c : s) {
            int ci = c - 'a';
            if (!ch[p][ci]) {
                ch[p][ci] = ++cnt;           // 新建节点
                memset(ch[cnt], 0, sizeof(ch[cnt]));
                exist[cnt] = false;
            }
            p = ch[p][ci];                    // 移动到下一个节点
        }
        exist[p] = true;  // 标记字符串末尾
    }
    
    // 查询字符串是否存在
    // 时间复杂度：O(|s|)
    bool find(const string& s) {
        int p = 0;  // 从根节点开始
        for (char c : s) {
            int ci = c - 'a';
            if (!ch[p][ci]) return false;  // 路径断了，不存在
            p = ch[p][ci];
        }
        return exist[p];  // 必须到达结尾标记的节点
    }
    
    // 查询是否有以 prefix 为前缀的字符串
    bool startsWith(const string& prefix) {
        int p = 0;
        for (char c : prefix) {
            int ci = c - 'a';
            if (!ch[p][ci]) return false;
            p = ch[p][ci];
        }
        return true;  // 路径存在即有此前缀（不需要 exist 标记）
    }
};

int main() {
    Trie trie;
    
    // 插入一些单词
    trie.insert("apple");
    trie.insert("app");
    trie.insert("apply");
    trie.insert("banana");
    
    // 查询
    cout << trie.find("apple")       << endl;  // 1（存在）
    cout << trie.find("app")         << endl;  // 1（存在）
    cout << trie.find("ap")          << endl;  // 0（路径存在，但没有标记）
    cout << trie.startsWith("ap")    << endl;  // 1（有以 "ap" 开头的字符串）
    cout << trie.startsWith("ban")   << endl;  // 1
    cout << trie.startsWith("cat")   << endl;  // 0
    
    return 0;
}

初始：只有根节点 0

插入 "app"：
  节点0 --'a'--> 节点1
  节点1 --'p'--> 节点2
  节点2 --'p'--> 节点3，exist[3] = true（"app" 结束）

插入 "apple"：
  节点0 --'a'--> 节点1（已存在，复用）
  节点1 --'p'--> 节点2（已存在，复用）
  节点2 --'p'--> 节点3（已存在，复用）
  节点3 --'l'--> 节点4（新建）
  节点4 --'e'--> 节点5，exist[5] = true（"apple" 结束）

现在 "app" 和 "apple" 共享前缀 "app"

// 增加 count 数组记录每个节点被经过的次数
// count[u] = 以 u 为前缀的字符串的总插入次数

int count_prefix[MAXN];  // count[u] = 经过节点 u 的次数

void insert_with_count(const string& s) {
    int p = 0;
    for (char c : s) {
        int ci = c - 'a';
        if (!ch[p][ci]) {
            ch[p][ci] = ++cnt;
            count_prefix[cnt] = 0;
        }
        p = ch[p][ci];
        count_prefix[p]++;  // 每经过一个节点，计数 +1
    }
    exist[p] = true;
}

// 查询有多少个已插入字符串以 prefix 为前缀
int count_starts_with(const string& prefix) {
    int p = 0;
    for (char c : prefix) {
        int ci = c - 'a';
        if (!ch[p][ci]) return 0;
        p = ch[p][ci];
    }
    return count_prefix[p];
}

// 01-Trie：维护整数集合，支持查询"与 x 异或最大的数"
// 按二进制位（从第30位到第0位）建树
const int BIT = 30;
const int MAXN_01 = 3000005;

int ch01[MAXN_01][2];  // 只有 0/1 两个子节点
int cnt01 = 0;

// 将整数 x 插入 01-Trie
void insert01(int x) {
    int p = 0;
    for (int i = BIT; i >= 0; i--) {
        int bit = (x >> i) & 1;       // 取第 i 位
        if (!ch01[p][bit]) ch01[p][bit] = ++cnt01;
        p = ch01[p][bit];
    }
}

// 查询与 x 异或值最大的数，返回最大异或值
int max_xor(int x) {
    int p = 0, res = 0;
    for (int i = BIT; i >= 0; i--) {
        int bit = (x >> i) & 1;
        int want = 1 - bit;            // 想要走与 bit 不同的方向（使异或为1）
        if (ch01[p][want]) {
            p = ch01[p][want];
            res |= (1 << i);           // 这一位异或为 1
        } else {
            p = ch01[p][bit];          // 没有理想方向，只能走 bit 方向
        }
    }
    return res;
}

// 示例：
// 集合 {3, 7, 9, 12}，查询与 6（二进制 110）异或最大
// 6 XOR 9 = 15（1111），是最大值
int main() {
    int arr[] = {3, 7, 9, 12};
    for (int x : arr) insert01(x);
    cout << max_xor(6) << endl;  // 输出 15
    return 0;
}

思路： 拼接 needle + '#' + haystack，计算前缀函数，找 π[i] == len(needle) 的位置。

#include <bits/stdc++.h>
using namespace std;

vector<int> prefix_function(const string& s) {
    int n = s.size();
    vector<int> pi(n, 0);
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
        if (s[i] == s[j]) j++;
        pi[i] = j;
    }
    return pi;
}

int strStr(string haystack, string needle) {
    if (needle.empty()) return 0;
    int m = needle.size(), n = haystack.size();
    auto pi = prefix_function(needle + '#' + haystack);
    for (int i = m + 1; i <= m + n; i++)
        if (pi[i] == m) return i - 2 * m;
    return -1;
}

int main() {
    cout << strStr("hello",  "ll")  << "\n";  // 2
    cout << strStr("aaaaa",  "bba") << "\n";  // -1
    cout << strStr("sadbutsad", "sad") << "\n";  // 0（第一次出现）
    return 0;
}

追踪（haystack="hello", needle="ll"）：

拼接串：  l l # h e l l o
π 值：    0 1 0 0 0 1 2 0
                        ↑ i=6，π[6]=2=len("ll") ✓
位置 = 6 - 2×2 = 2

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000005;
int ch[MAXN][26];
bool exist[MAXN];
int tot = 0;

void insert(const string& s) {
    int p = 0;
    for (char c : s) {
        int ci = c - 'a';
        if (!ch[p][ci]) {
            ch[p][ci] = ++tot;
            fill(ch[tot], ch[tot] + 26, 0);
            exist[tot] = false;
        }
        p = ch[p][ci];
    }
    exist[p] = true;
}

bool query(const string& s) {
    int p = 0;
    for (char c : s) {
        int ci = c - 'a';
        if (!ch[p][ci]) return false;
        p = ch[p][ci];
    }
    return exist[p];
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n, q;
    cin >> n;
    for (int i = 0; i < n; i++) {
        string w; cin >> w;
        insert(w);
    }
    cin >> q;
    while (q--) {
        string w; cin >> w;
        cout << (query(w) ? "YES" : "NO") << "\n";
    }
    return 0;
}

方法 1（排序法）： 排序后只比较第一个和最后一个字符串的前缀，因为它们字典序差距最大，LCP 最短。

#include <bits/stdc++.h>
using namespace std;

string longestCommonPrefix(vector<string>& strs) {
    if (strs.empty()) return "";
    sort(strs.begin(), strs.end());
    string& first = strs.front();
    string& last  = strs.back();
    int i = 0;
    while (i < (int)first.size() && i < (int)last.size() && first[i] == last[i])
        i++;
    return first.substr(0, i);
}

int main() {
    vector<string> v = {"flower", "flow", "flight"};
    cout << longestCommonPrefix(v) << "\n";  // "fl"
    v = {"dog", "racecar", "car"};
    cout << longestCommonPrefix(v) << "\n";  // ""
    return 0;
}

方法 2（Trie法）： 将所有字符串插入 Trie，从根节点出发沿唯一路径走，直到遇到分叉或终止标记。

string lcp_trie(vector<string>& strs) {
    // 插入所有字符串后，从根出发找只有一个非空子节点且不是末尾的最长路径
    for (auto& s : strs) insert(s);
    
    string result = "";
    int p = 0;
    while (true) {
        if (exist[p]) break;  // 某字符串在此结束，不能继续
        int next = -1, cnt = 0;
        for (int i = 0; i < 26; i++) {
            if (ch[p][i]) { next = i; cnt++; }
        }
        if (cnt != 1) break;  // 有分叉，停止
        result += (char)('a' + next);
        p = ch[p][next];
    }
    return result;
}

核心公式： T = n - π[n-1]，当 n % T == 0 时字符串可被整除，否则最小周期为 n。

#include <bits/stdc++.h>
using namespace std;

vector<int> prefix_function(const string& s) {
    int n = s.size();
    vector<int> pi(n, 0);
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
        if (s[i] == s[j]) j++;
        pi[i] = j;
    }
    return pi;
}

int min_period(const string& s) {
    int n = s.size();
    auto pi = prefix_function(s);
    int T = n - pi[n - 1];
    return (n % T == 0) ? T : n;
}

int main() {
    cout << min_period("abcabc")   << "\n";  // 3
    cout << min_period("abababab") << "\n";  // 2
    cout << min_period("abcd")     << "\n";  // 4
    cout << min_period("aaaaaa")   << "\n";  // 1
    return 0;
}

原理解释： π[n-1] = k 意味着字符串前 k 个字符 = 后 k 个字符。
若 s 有周期 T，则 π[n-1] ≥ n-T，等价于 T ≤ n - π[n-1]。
n - π[n-1] 正是最小的满足条件的 T。

思路： 将所有数插入 01-Trie，然后对每个数 x 查询「与 x 异或最大的数」并取全局最大值。

#include <bits/stdc++.h>
using namespace std;

const int BIT = 30;
const int MAXN = 3200005;
int ch[MAXN][2];
int tot = 0;

void insert(int x) {
    int p = 0;
    for (int i = BIT; i >= 0; i--) {
        int b = (x >> i) & 1;
        if (!ch[p][b]) ch[p][b] = ++tot;
        p = ch[p][b];
    }
}

int max_xor_with(int x) {
    int p = 0, res = 0;
    for (int i = BIT; i >= 0; i--) {
        int b = (x >> i) & 1;
        int want = 1 - b;  // 想走异位，使该位异或为 1
        if (ch[p][want]) {
            res |= (1 << i);
            p = ch[p][want];
        } else {
            p = ch[p][b];
        }
    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    
    int n; cin >> n;
    vector<int> nums(n);
    for (int& x : nums) { cin >> x; insert(x); }
    
    int ans = 0;
    for (int x : nums)
        ans = max(ans, max_xor_with(x));
    cout << ans << "\n";
    return 0;
}

追踪（nums = [3, 10, 5, 25, 2, 8]，查询 5 = 0b000101）：

插入所有数后对 5 查询：
位30~5：全0，Trie也全0，只能往0走
位4(x=0)：want=1，Trie中有1（25=11001的第4位=1）→ 走1，res+=16
位3(x=0)：want=1，Trie中有1（25的第3位=1）→ 走1，res+=8
位2(x=1)：want=0，Trie中有0（25的第2位=0）→ 走0，res+=4
位1(x=0)：want=1，无1路 → 走0
位0(x=1)：want=0，有0路（25的第0位=1，走不了） → 走1

res = 16+8+4 = 28 = 5 XOR 25 ✓

思路： 将所有号码插入 Trie，若插入过程中遇到已有终止标记的节点（当前号码是已插入号码的延伸），或插入完后该节点还有子节点（已插入号码是当前号码的前缀），则存在冲突。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000005;
int ch[MAXN][10];  // 数字 0~9
bool is_end[MAXN];
int tot = 0;

// 插入号码，返回是否发现冲突
bool insert_check(const string& s) {
    int p = 0;
    for (char c : s) {
        int d = c - '0';
        if (is_end[p]) return true;   // 已有号码是当前号码的前缀
        if (!ch[p][d]) {
            ch[p][d] = ++tot;
            fill(ch[tot], ch[tot] + 10, 0);
            is_end[tot] = false;
        }
        p = ch[p][d];
    }
    // 插入完成，检查该节点是否已有子节点（当前号码是已有号码的前缀）
    for (int i = 0; i < 10; i++)
        if (ch[p][i]) return true;
    is_end[p] = true;
    return false;
}

int main() {
    int n; cin >> n;
    bool conflict = false;
    for (int i = 0; i < n; i++) {
        string s; cin >> s;
        if (insert_check(s)) conflict = true;
    }
    cout << (conflict ? "NO" : "YES") << "\n";
    return 0;
}

思路： 枚举所有子串，用 set<pair<哈希值, 长度>> 标记已统计过的，对每个子串用 KMP 统计出现次数。

#include <bits/stdc++.h>
using namespace std;

vector<int> prefix_function(const string& s) {
    int n = s.size();
    vector<int> pi(n, 0);
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
        if (s[i] == s[j]) j++;
        pi[i] = j;
    }
    return pi;
}

int count_occurrences(const string& text, const string& pattern) {
    if (pattern.empty()) return 0;
    int m = pattern.size();
    auto pi = prefix_function(pattern + '#' + text);
    int cnt = 0;
    for (int i = m + 1; i < (int)pi.size(); i++)
        if (pi[i] == m) cnt++;
    return cnt;
}

int main() {
    string s; cin >> s;
    int n = s.size();
    
    set<string> counted;  // 已统计的子串
    int ans = 0;
    
    for (int i = 0; i < n; i++) {
        for (int len = 1; len <= n - i; len++) {
            string sub = s.substr(i, len);
            if (counted.count(sub)) continue;
            counted.insert(sub);
            if (count_occurrences(s, sub) >= 2) ans++;
        }
    }
    
    cout << ans << "\n";
    return 0;
}

注： 上面方法对小数据（n ≤ 1000）可行，大数据需用后缀数组或后缀自动机优化至 O(N log N)。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const int BIT = 30;
const int TRIE_MAXN = MAXN * 31 * 2;

// 01-Trie
int ch_trie[TRIE_MAXN][2];
int tot_trie = 0;

void insert_trie(int x) {
    int p = 0;
    for (int i = BIT; i >= 0; i--) {
        int b = (x >> i) & 1;
        if (!ch_trie[p][b]) ch_trie[p][b] = ++tot_trie;
        p = ch_trie[p][b];
    }
}

int max_xor_trie(int x) {
    int p = 0, res = 0;
    for (int i = BIT; i >= 0; i--) {
        int b = (x >> i) & 1;
        int want = 1 - b;
        if (ch_trie[p][want]) { res |= (1 << i); p = ch_trie[p][want]; }
        else p = ch_trie[p][b];
    }
    return res;
}

// 树 DFS
vector<pair<int,int>> adj[MAXN];
int dist[MAXN];  // dist[i] = 根到 i 的异或距离

void dfs(int u, int parent) {
    insert_trie(dist[u]);
    for (auto [v, w] : adj[u]) {
        if (v == parent) continue;
        dist[v] = dist[u] ^ w;
        dfs(v, u);
    }
}

int main() {
    int n; cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    
    dist[1] = 0;
    dfs(1, -1);  // 从节点 1 出发 DFS
    
    // 对每个节点，在 Trie 中找与其异或最大的节点
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans = max(ans, max_xor_trie(dist[i]));
    
    cout << ans << "\n";
    return 0;
}

关键原理：
设 d[u] = 根到 u 的边权异或和。
路径 u → v 的异或和 = d[u] XOR d[v]（因为公共前缀部分异或两次等于 0）。
所以只需在所有 d[i] 中找最大异或对，01-Trie 做到 O(N log W)。