Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Light OJ: 1427 - Substring Frequency (II)
/* Copyright 2017 Rafael Rendón Pablo <rafaelrendonpablo@gmail.com> */
// 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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.