KMP 알고리즘의 nxt 배열을 살펴보겠습니다. 답은 n - nxt[n]으로 구할 수 있습니다.

코드

#include <iostream>
#include <vector>
#include <string>

void compute_next_array(int n, const std::string& s, std::vector<int>& nxt) {
    int j = 0;
    for (int i = 1; i < n; ++i) {
        while (j > 0 && s[i] != s[j]) {
            j = nxt[j - 1];
        }
        if (s[i] == s[j]) {
            j++;
        }
        nxt[i] = j;
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int n;
    std::cin >> n;
    std::string a;
    std::cin >> a;

    std::vector<int> nxt(n);
    compute_next_array(n, a, nxt);

    std::cout << n - nxt[n - 1] << std::endl;

    return 0;
}

문자열 연결과 접두사 특징을 고려할 때 KMP 알고리즘을 다시 활용할 수 있습니다. 이 문제는 가장 긴 주기를 요구하므로, 남은 부분을 최소화해야 합니다. 따라서 nxt' 배열을 직접 구할 수 있습니다. 기본 원리는 동일합니다. j는 종종 nxt[i]와 같다는 것을 알 수 있습니다. 이를 통해 다음과 같은 점화식을 유도할 수 있습니다: nxt[i] = (nxt[nxt'[i]] == 0) ? fail_i : nxt[nxt'[i]] 어떤 경우에는 주기가 존재하지 않아 nxt'[i] < i / 2가 될 수 있습니다. 이 경우 ans를 업데이트하지 않으면 됩니다. 데이터 범위가 10^6이므로, 최대 ans는 10^12가 될 수 있어 long long 타입이 필요합니다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <numeric>

void compute_kmp_arrays(int n, const std::string& s, std::vector<int>& fail, std::vector<int>& nxt) {
    int j = 0;
    for (int i = 1; i < n; ++i) {
        while (j > 0 && s[i] != s[j]) {
            j = fail[j - 1];
        }
        if (s[i] == s[j]) {
            j++;
        }
        fail[i] = j;
    }

    j = 0;
    for (int i = 1; i < n; ++i) {
        j = fail[i];
        nxt[i] = (j == 0) ? fail[i] : nxt[j - 1];
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int n;
    std::cin >> n;
    std::string a;
    std::cin >> a;

    std::vector<int> fail(n);
    std::vector<int> nxt(n);
    compute_kmp_arrays(n, a, fail, nxt);

    long long total_period_sum = 0;
    for (int i = 0; i < n; ++i) {
        int current_period_len = (i + 1) - nxt[i];
        if (current_period_len >= std::ceil((i + 1) / 2.0) && nxt[i] > 0) {
            total_period_sum += current_period_len;
        }
    }

    std::cout << total_period_sum << std::endl;

    return 0;
}

문제: 최소한의 문자를 추가하여 문자열을 회문으로 만드세요. 전체 문자열의 끝에 닿는 가장 긴 접두사를 계산하면 됩니다. 즉, i + r[i] - 1 = n인 경우입니다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int n;
    std::cin >> n;
    std::string s;
    std::cin >> s;

    std::string reversed_s = s;
    std::reverse(reversed_s.begin(), reversed_s.end());
    std::string combined = s + "#" + reversed_s;

    int m = combined.length();
    std::vector<int> pi(m);
    for (int i = 1; i < m; i++) {
        int j = pi[i - 1];
        while (j > 0 && combined[i] != combined[j]) {
            j = pi[j - 1];
        }
        if (combined[i] == combined[j]) {
            j++;
        }
        pi[i] = j;
    }

    int longest_palindrome_suffix_prefix = pi[m - 1];
    int chars_to_add = n - longest_palindrome_suffix_prefix;

    std::cout << chars_to_add << std::endl;

    return 0;
}

DFS를 사용하여 트리의 모든 노드에서 루트까지의 XOR 합을 계산합니다. 노드 u에서 노드 v까지의 XOR 합은 루트까지의 XOR 합과 같습니다. 따라서 s[i] XOR s[j]를 최대화하는 것을 목표로 합니다. 각 s[i]에 대해 s[i] XOR s[j]를 최대화하는 s[j]를 찾습니다. 이는 트라이(Trie)에서 수행할 수 있습니다. 모든 s[i]를 바이너리 문자열로 트라이에 삽입합니다. 탐욕적 접근: 트라이에서 s[i]와 다른 비트를 가진 값이 존재하면 해당 경로를 따릅니다. 그렇지 않으면 같은 값을 가진 경로를 따릅니다. 상위 비트의 1은 하위 비트의 1의 합보다 항상 크므로 탐욕적 선택이 유효합니다. 모든 s[i]에 대해 최대 XOR 값을 찾습니다. 시간 복잡도는 O(n log α)이며, 여기서 α는 비트 수입니다. 세부 정보: 선행 0을 추가해야 합니다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

const int MAX_BITS = 31; // Assuming 32-bit integers

struct TrieNode {
    TrieNode* children[2];
    TrieNode() {
        children[0] = children[1] = nullptr;
    }
};

void insert(TrieNode* root, int num) {
    TrieNode* curr = root;
    for (int i = MAX_BITS - 1; i >= 0; --i) {
        int bit = (num >> i) & 1;
        if (curr->children[bit] == nullptr) {
            curr->children[bit] = new TrieNode();
        }
        curr = curr->children[bit];
    }
}

int find_max_xor(TrieNode* root, int num) {
    TrieNode* curr = root;
    int max_xor_val = 0;
    for (int i = MAX_BITS - 1; i >= 0; --i) {
        int bit = (num >> i) & 1;
        int desired_bit = 1 - bit;
        if (curr->children[desired_bit] != nullptr) {
            max_xor_val |= (1 << i);
            curr = curr->children[desired_bit];
        } else {
            curr = curr->children[bit];
        }
    }
    return max_xor_val;
}

std::vector<int> adj[100005];
int xor_sums[100005];

void dfs(int u, int p, int current_xor) {
    xor_sums[u] = current_xor;
    for (auto& edge : adj[u]) {
        int v = edge.first;
        int weight = edge.second;
        if (v != p) {
            dfs(v, u, current_xor ^ weight);
        }
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    for (int i = 0; i < n - 1; ++i) {
        int u, v, w;
        std::cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    dfs(1, 0, 0);

    TrieNode* root = new TrieNode();
    int max_overall_xor = 0;

    for (int i = 1; i <= n; ++i) {
        insert(root, xor_sums[i]);
        max_overall_xor = std::max(max_overall_xor, find_max_xor(root, xor_sums[i]));
    }

    std::cout << max_overall_xor << std::endl;

    return 0;
}

연결된 리스트를 만들고, 분할 정복 기법을 사용하여 접미사 배열을 계산하면 O(n log^2 n) 시간 복잡도로 해결할 수 있습니다. 접미사 배열 구현은 비교적 간단합니다.