Light OJ: 1427 - Substring Frequency (II)

substring_frequence_ii.cpp

/* Copyright 2017 Rafael Rendón Pablo <[email protected]> */
// region Template
#include <bits/stdc++.h>
using namespace std;
typedef long long           int64;
typedef unsigned long long  uint64;
const double kEps = 10e-8;
const int kMax = 1000;
const int kInf = 1 << 30;
const int kFail = -1;
// endregion
int trie[kMax][26+1];
int fail[kMax];
vector<int> output[kMax];
int newState;

void add(const string& word, int index) {
    int state = 0;
    for (int i = 0; i < int(word.length()); i++) {
        int c = word[i] - 'a';
        if (trie[state][c] == kFail) {
            newState++;
            trie[state][c] = newState;
            state = newState;
        } else {
            state = trie[state][c];
        }
    }
    output[state].push_back(index);
}


void init() {
    memset(trie, kFail, sizeof trie);
    memset(fail, kFail, sizeof fail);
    for (int i = 0; i < kMax; i++) {
        output[i].clear();
    }
    newState = 0;
}

void buildTrie(const vector<string>& words) {
    for (int i = 0; i < int(words.size()); i++) {
        add(words[i], i);
    }
    for (int a = 0; a < 26; a++) {
        if (trie[0][a] == kFail) {
            trie[0][a] = 0;
        }
    }
}

void buildFailFunction() {
    queue<int> Q;
    for (char a = 0; a < 26; a++) {
        int s = trie[0][a];
        if (s != 0) {
            Q.push(s);
            fail[s] = 0;
        }
    }

    while (!Q.empty()) {
        int r = Q.front();
        Q.pop();
        for (char a = 0; a < 26; a++) {
            int s = trie[r][a];
            if (s == kFail) {
                continue;
            }
            Q.push(s);
            int state = 0;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tests;
    cin >> tests;
    for (int tc = 1; tc <= tests; tc++) {
        int n;
        string text;
        cin >> n >> text;
        vector<string> words(n);
        for (string& word : words) {
            cin >> word;
        }
        init();
        buildTrie(words);
        buildFailFunction();
    }
    return EXIT_SUCCESS;
}