mickypinata

USACO-T030: Longest Prefix

Dec 1st, 2021
619
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. ID: mickyta1
  3. TASK: prefix
  4. LANG: C++
  5. */
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9.  
  10. const int N = 2e5 + 5;
  11. const int L = 76 + 5;
  12. const int A = 26;
  13.  
  14. bool dp[N];
  15. char tmp[L];
  16.  
  17. struct node {
  18.     bool isWord;
  19.     node *nxt[A];
  20.     node(){
  21.         isWord = false;
  22.         for(int i = 0; i < A; ++i){
  23.             nxt[i] = NULL;
  24.         }
  25.     }
  26. };
  27.  
  28. struct trie {
  29.     node *root;
  30.     trie(){
  31.         printStr = "";
  32.         root = new node();
  33.     }
  34.     void addWord(string &str){
  35.         addWord(str, 0, root);
  36.     }
  37.     void print(){
  38.         print(root);
  39.     }
  40. private:
  41.     void addWord(string &str, int i, node *root){
  42.         if(i == str.size()){
  43.             root -> isWord = true;
  44.             return;
  45.         }
  46.         int c = str[i] - 'A';
  47.         if(root -> nxt[c] == NULL){
  48.             root -> nxt[c] = new node();
  49.         }
  50.         addWord(str, i + 1, root -> nxt[c]);
  51.     }
  52.     string printStr;
  53.     void print(node *root){
  54.         if(root -> isWord){
  55.             cout << printStr << '\n';
  56.         }
  57.         for(int i = 0; i < A; ++i){
  58.             if(root -> nxt[i] != NULL){
  59.                 printStr.push_back((char)(i + 'A'));
  60.                 print(root -> nxt[i]);
  61.                 printStr.pop_back();
  62.             }
  63.         }
  64.     }
  65. };
  66.  
  67. int main(){
  68.     freopen("prefix.in", "r", stdin);
  69.     freopen("prefix.out", "w", stdout);
  70.  
  71.     trie tr = trie();
  72.     string str;
  73.     while(true){
  74.         scanf(" %s", tmp);
  75.         if(tmp[0] == '.'){
  76.             break;
  77.         }
  78.         str = tmp;
  79.         reverse(str.begin(), str.end());
  80.         tr.addWord(str);
  81.     }
  82.     str = "";
  83.     while(scanf(" %s", tmp) != EOF){
  84.         str += tmp;
  85.     }
  86.     int n = str.size();
  87.     str = 'A' + str;
  88.     int mx = 0;
  89.     dp[0] = true;
  90.     for(int i = 1; i <= n; ++i){
  91.         node *cur = tr.root;
  92.         dp[i] = false;
  93.         for(int j = i; j >= 1; --j){
  94.             int c = str[j] - 'A';
  95.             if(cur -> nxt[c] == NULL){
  96.                 break;
  97.             }
  98.             cur = cur -> nxt[c];
  99.             if(cur -> isWord){
  100.                 dp[i] |= dp[j - 1];
  101.             }
  102.         }
  103.         if(dp[i]){
  104.             mx = max(mx, i);
  105.         }
  106.     }
  107.     cout << mx << '\n';
  108.  
  109.     fclose(stdin);
  110.     fclose(stdout);
  111.     return 0;
  112. }
  113.  
RAW Paste Data