fork download
copy 
  1. //#include <bits/stdc++.h>
  2.  
  3. #include <iostream>
  4. #include <vector>
  5. #include <array>
  6.  
  7. using namespace std;
  8.  
  9. #define FOR(i,a,b)      for (int i = (a), _b = (b); i <= (_b); ++i)
  10. #define FORD(i,a,b)     for (int i = (a), _b = (b); i >= (_b); --i)
  11.  
  12. //--Compare------------------------------------------------------------------------------------
  13. template<class X, class Y>
  14.     inline bool maximize(X &x, const Y &y){ return (x < y) ? x = y, 1 : 0; }
  15.  
  16. template<class X, class Y>
  17.     inline bool minimize(X &x, const Y &y){ return (x > y) ? x = y, 1 : 0; }
  18.  
  19. //--Process------------------------------------------------------------------------------------
  20.  
  21. typedef pair <int, int>   pii;
  22. #define fi              first
  23. #define se              second
  24.  
  25. constexpr int MAXN = 2e5 + 10;
  26. constexpr pii INF = {1e9, 1e9};
  27.  
  28. int n, m, q;
  29. string P[MAXN >> 1];
  30. int idx[MAXN];
  31.  
  32. vector <array<int, 26>> nxt[MAXN >> 1];
  33. int sz[MAXN], nxtAll[26][MAXN];
  34. pii dp[2][3005];
  35.  
  36. void init(void)
  37. {
  38.     static array <int, 26> INF_AR;
  39.     FOR(c, 0, 25) INF_AR[c] = (int) (1e9);
  40.  
  41.     // nxt[i][j][c] la vi tri k nho nhat > j sao cho P[i][k] = c (1 <= i <= n)
  42.     // (x, y)
  43.     FORD(i, n, 0)
  44.     {
  45.         sz[i] = P[i].size();
  46.         P[i] = '#' + P[i] + '#';
  47.  
  48.         nxt[i].assign(sz[i] + 2, INF_AR);
  49.  
  50.         FOR(c, 0, 25)
  51.         {
  52.             FORD(j, sz[i], 0)
  53.             {
  54.                 if (P[i][j + 1] - 'a' == c) nxt[i][j][c] = j + 1;
  55.                 else nxt[i][j][c] = nxt[i][j + 1][c];
  56.             }
  57.         }
  58.     }
  59.  
  60.     FOR(c, 0, 25) nxtAll[c][m] = m + 2;
  61.     FORD(i, m - 1, 0)
  62.     {
  63.         FOR(c, 0, 25)
  64.         {
  65.             if (nxt[idx[i + 1]][0][c] <= sz[idx[i + 1]])
  66.                 nxtAll[c][i] = i + 1;
  67.             else
  68.                 nxtAll[c][i] = nxtAll[c][i + 1];
  69.         }
  70.     }
  71. }
  72.  
  73. void solve(void)
  74. {
  75.     while (q--)
  76.     {
  77.         string S; cin >> S;
  78.         int szS = S.size();
  79.         S = '#' + S + '#';
  80.  
  81.         dp[0][0] = {0, 0};
  82.         dp[0][1] = dp[0][2] = INF;
  83.  
  84.         int res = 0;
  85.  
  86.         FOR(i, 1, szS)
  87.         {
  88.             FOR(len, 0, i + 1) dp[i & 1][len] = INF;
  89.             FOR(len, 0, i)
  90.             {
  91.                 minimize(dp[i & 1][len], dp[(i - 1) & 1][len]);
  92.                 int x = dp[(i - 1) & 1][len].fi, k = dp[(i - 1) & 1][len].se;
  93.                 if (x < 0 || x > m) continue;
  94.  
  95.                 if (x != 0 && nxt[idx[x]][k][S[i] - 'a'] <= sz[idx[x]])
  96.                     minimize(dp[i & 1][len + 1], pii{x, nxt[idx[x]][k][S[i] - 'a']});
  97.  
  98.                 if (x == 0 || nxt[idx[x]][k][S[i] - 'a'] > sz[idx[x]])
  99.                 {
  100.                     x = nxtAll[S[i] - 'a'][x];
  101.                     if (x <= m)
  102.                         minimize(dp[i & 1][len + 1], pii{x, nxt[idx[x]][0][S[i] - 'a']});
  103.                 }
  104.  
  105.                 if (i == szS && dp[i & 1][len].fi <= m) res = len;
  106.                 if (i == szS && dp[i & 1][len + 1].fi <= m) res = len + 1;
  107.             }
  108.         }
  109.  
  110.         cout << res << '\n';
  111.     }
  112.     cout << '\n';
  113. }
  114.  
  115.  
  116. signed main(void)
  117. {
  118.     cin.tie(nullptr)->sync_with_stdio(false);
  119.  
  120.     #define task "ojfactory"
  121.     if (fopen(task".INP", "r"))
  122.     {
  123.        freopen(task".INP", "r", stdin);
  124.        freopen(task".OUT", "w", stdout);
  125.     }
  126.     //--OpenFile-------------------------------------------------------------------------------
  127.  
  128.     cin >> n >> m >> q;
  129.     FOR(i, 1, n) cin >> P[i];
  130.     FOR(i, 1, m) cin >> idx[i];
  131.     P[0] = "";
  132.  
  133.     init();
  134.     solve();
  135.  
  136.     return 0;
  137. }
  138.  
Success #stdin #stdout 0.01s 30312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/HBiX2T
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++ (gcc 8.3)

					

					

						
created:
								
						
6 days 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!