USACO-T030: Longest Prefix

/*
ID: mickyta1
TASK: prefix
LANG: C++
*/

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

const int N = 2e5 + 5;
const int L = 76 + 5;
const int A = 26;

bool dp[N];
char tmp[L];

struct node {
    bool isWord;
    node *nxt[A];
    node(){
        isWord = false;
        for(int i = 0; i < A; ++i){
            nxt[i] = NULL;
        }
    }
};

struct trie {
    node *root;
    trie(){
        printStr = "";
        root = new node();
    }
    void addWord(string &str){
        addWord(str, 0, root);
    }
    void print(){
        print(root);
    }
private:
    void addWord(string &str, int i, node *root){
        if(i == str.size()){
            root -> isWord = true;
            return;
        }
        int c = str[i] - 'A';
        if(root -> nxt[c] == NULL){
            root -> nxt[c] = new node();
        }
        addWord(str, i + 1, root -> nxt[c]);
    }
    string printStr;
    void print(node *root){
        if(root -> isWord){
            cout << printStr << '\n';
        }
        for(int i = 0; i < A; ++i){
            if(root -> nxt[i] != NULL){
                printStr.push_back((char)(i + 'A'));
                print(root -> nxt[i]);
                printStr.pop_back();
            }
        }
    }
};

int main(){
    freopen("prefix.in", "r", stdin);
    freopen("prefix.out", "w", stdout);

    trie tr = trie();
    string str;
    while(true){
        scanf(" %s", tmp);
        if(tmp[0] == '.'){
            break;
        }
        str = tmp;
        reverse(str.begin(), str.end());
        tr.addWord(str);
    }
    str = "";
    while(scanf(" %s", tmp) != EOF){
        str += tmp;
    }
    int n = str.size();
    str = 'A' + str;
    int mx = 0;
    dp[0] = true;
    for(int i = 1; i <= n; ++i){
        node *cur = tr.root;
        dp[i] = false;
        for(int j = i; j >= 1; --j){
            int c = str[j] - 'A';
            if(cur -> nxt[c] == NULL){
                break;
            }
            cur = cur -> nxt[c];
            if(cur -> isWord){
                dp[i] |= dp[j - 1];
            }
        }
        if(dp[i]){
            mx = max(mx, i);
        }
    }
    cout << mx << '\n';

    fclose(stdin);
    fclose(stdout);
    return 0;
}