fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define Task "LAUGH"
  5. #define signed main() main()
  6. #define sp " "
  7. #define endl "\n"
  8. #define sz(x) (int)x.size()
  9. #define all(x) x.begin(), x.end()
  10. #define mp(x, y) make_pair(x, y)
  11. #define F first
  12. #define S second
  13.  
  14. typedef long long ll;
  15. typedef long double ld;
  16. typedef pair<int, int> pii;
  17. typedef vector<int> vi;
  18.  
  19. constexpr int maxn = 1e5 + 5;
  20.  
  21. int n, m;
  22. string s, p;
  23. int dp[maxn];
  24.  
  25. struct Node {
  26.     int child[4];
  27.     int link;
  28.     vector<int> out;
  29.     Node() {
  30.         memset(child, -1, sizeof(child));
  31.         link = 0;
  32.     }
  33. };
  34.  
  35. vector<Node> tries;
  36.  
  37. int GetId(char ch) {
  38.     if(ch == 'a') return 0;
  39.     if(ch == 'h') return 1;
  40.     if(ch == 'c') return 2;
  41.     return 3;
  42. }
  43.  
  44. main() {
  45.     ios_base::sync_with_stdio(0);
  46.     cin.tie(0);
  47.  
  48.     if(fopen(Task".inp", "r")) {
  49.         freopen(Task".inp", "r", stdin);
  50.         freopen(Task".out", "w", stdout);
  51.     }
  52.  
  53.     cin >> n >> s;
  54.     m = sz(s);
  55.     tries.emplace_back();
  56.  
  57.     for(int i = 1; i <= n; i++) {
  58.         cin >> p;
  59.         int cur = 0;
  60.         for(char c : p) {
  61.             int x = GetId(c);
  62.             if(tries[cur].child[x] == -1) {
  63.                 tries[cur].child[x] = sz(tries);
  64.                 tries.emplace_back();
  65.             }
  66.             cur = tries[cur].child[x];
  67.         }
  68.         tries[cur].out.push_back(sz(p));
  69.     }
  70.  
  71.     queue<int> q;
  72.  
  73.     for(int i = 0; i <= 3; i++) {
  74.         int cur = tries[0].child[i];
  75.         if(cur != -1) {
  76.             tries[cur].link = 0;
  77.             q.push(cur);
  78.         } else {
  79.             tries[0].child[i] = 0;
  80.         }
  81.     }
  82.  
  83.     while(!q.empty()) {
  84.         int u = q.front(); q.pop();
  85.         for(int i = 0; i <= 3; i++) {
  86.             int v = tries[u].child[i];
  87.             if(v != -1) {
  88.                 tries[v].link = tries[tries[u].link].child[i];
  89.                 for(int l : tries[tries[v].link].out)
  90.                     tries[v].out.push_back(l);
  91.                 q.push(v);
  92.             } else {
  93.                 tries[u].child[i] = tries[tries[u].link].child[i];
  94.             }
  95.         }
  96.     }
  97.  
  98.     vector<vi> luu(m + 1);
  99.     int cur = 0;
  100.     for(int i = 1; i <= m; i++) {
  101.         cur = tries[cur].child[GetId(s[i - 1])];
  102.         for(int l : tries[cur].out) {
  103.             luu[i].push_back(l);
  104.         }
  105.     }
  106.  
  107.     int ans = 0;
  108.  
  109.     for(int i = 1; i <= m; i++) {
  110.         memset(dp, 0, sizeof(dp));
  111.         dp[i - 1] = 1;
  112.         for(int j = i; j <= m; j++) {
  113.             for(int l : luu[j]) {
  114.                 if(j - l >= i - 1 && dp[j - l]) {
  115.                     dp[j] = 1;
  116.                     break;
  117.                 }
  118.             }
  119.             if(dp[j]) {
  120.                 ans = max(ans, j - i + 1);
  121.             }
  122.         }
  123.     }
  124.  
  125.     cout << ans << endl;
  126.     return 0;
  127. }
  128.  
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/U7NlHA
language:
C++ (gcc 8.3)
created:
10 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!