Advertisement
erek1e

IOI '96 P5 - Longest Prefix

Jun 6th, 2022
652
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.63 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <set>
  5.  
  6. using namespace std;
  7.  
  8. const int MAX_LEN = 10;
  9.  
  10. int main() {
  11.     set<string> primitives;
  12.     string s, t;
  13.     while (cin >> t && t != ".") primitives.insert(t);
  14.     while (cin >> t) s += t;
  15.     vector<bool> can(1+s.size());
  16.     can[0] = true;
  17.     int longest;
  18.     for (int i = 0; i <= s.size(); ++i) {
  19.         if (!can[i]) continue;
  20.         longest = i;
  21.         for (int j = 1; j <= MAX_LEN && i+j <= s.size(); ++j) {
  22.             if (primitives.count(s.substr(i, j))) can[i+j] = true;
  23.         }
  24.     }
  25.     cout << longest << endl;
  26.     return 0;
  27. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement