uva 11488 - Hyper 접두사 세트 (사전 트 리)

제목 링크: uva 11488 - Hyper 접두사 세트
제목: 01 로 구 성 된 문자열 을 몇 개 주 고 접두사 문자열 을 구 합 니 다. 길 이 는 k 이 고 n 개의 문자열 에 나타 나 며 출력 이 가장 큰 k * n 입 니 다.
문제 풀이 방향: 사전 트 리 를 만 들 고 노드 에 횟수 를 기록 하면 됩 니 다.유지 보수 최대 치.

#include 
#include 
#include 
#include 

using namespace std;
const int maxn = 10000000;

struct Tire {
    int sz;
    int ans;
    int node[maxn][2];
    int val[maxn];

    void init();
    int idx(char ch);
    void insert(char* s);
}tree;

int main () {
    int cas, n;
    char str[205];
    scanf("%d", &cas);
    while (cas--) {
        tree.init();
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%s", str);
            tree.insert(str);
        }

        printf("%d
", tree.ans);
    }
    return 0;
}

void Tire::init() {
    sz = 1;
    ans = 0;
    memset(val, 0, sizeof(val));
    memset(node[0], 0, sizeof(node[0]));
}

int Tire::idx(char ch) {
    return ch - '0';
}

void Tire::insert(char* s) {
    int n = strlen(s), u = 0;
    for (int i = 0; i < n; i++) {
        int v = idx(s[i]);

        if (node[u][v] == 0) {
            memset(node[sz], 0, sizeof(node[sz]));
            node[u][v] = sz++;
        }
        u = node[u][v];
        val[u] += (i + 1);
        ans = max(ans, val[u]);
    }
}