Advertisement
Guest User

Untitled

a guest
Oct 24th, 2014
111
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.37 KB | None | 0 0
  1.  
  2.  
  3. #include <iostream>
  4. #include <cstdio>
  5. #include <algorithm>
  6. #include <cmath>
  7. #include <vector>
  8. #include <algorithm>
  9. #include <cstring>
  10. #include <string>
  11. #include <set>
  12. #include <map>
  13.  
  14. using namespace std;
  15.  
  16. char s[2005], p[505];
  17. int n, m, q = 0, mq = 0;
  18. const int INF = 100005;
  19. int arr[2005];
  20. int sum[2005];
  21. bool del[2005];
  22. bool usd[2005];
  23.  
  24. int cnt(int id)
  25. {
  26.     if(arr[id] > n)
  27.         return INF;
  28.     int rsum = sum[arr[id]-1];
  29.     int lsum = id ? sum[id-1] : 0;
  30.     return rsum - lsum;
  31. }
  32.  
  33. int main() {
  34.  
  35.     scanf("%s%s", s, p);
  36.     n = strlen(s);
  37.     m = strlen(p);
  38.  
  39.     for(int i = 0; i < n; ++i)
  40.     {
  41.         int j = i, id = 0;
  42.         for(; j < n && id < m; ++j)
  43.         {
  44.             if(s[j] == p[id])
  45.                 ++id;
  46.         }
  47.         arr[i] = (id == m ? j : INF);
  48.     }
  49.  
  50.     for(int i = 0; i < n; ++i)
  51.         sum[i] = (i ? sum[i-1] : 0) + (!del[i]);
  52.  
  53.     for(int i = 0; i < n; )
  54.     {
  55.         if(arr[i] != INF) ++mq;
  56.         i = arr[i];
  57.     }
  58.  
  59.     int it = 0;
  60.     while(q < mq)
  61.     {
  62.         /*cout << "ARR\n";
  63.         for(int i = 0; i < n; ++i)
  64.             cout << arr[i] << " ";
  65.         cout << endl;
  66.         cout << "DEL\n";
  67.         for(int i = 0; i < n; ++i)
  68.             cout << del[i] << " ";
  69.         cout << endl;
  70.         cout << "SUM\n";
  71.         for(int i = 0; i < n; ++i)
  72.             cout << sum[i] << " ";
  73.         cout << endl;
  74.         cout << "CNT\n";
  75.         for(int i = 0; i < n; ++i)
  76.             cout << cnt(i) << " ";
  77.         cout << endl;
  78.         fflush(stdout);*/
  79.  
  80.         int mi = -1;
  81.         for(int i = 0; i < n; ++i)
  82.             if(mi == -1 || (!del[i] && cnt(i) < cnt(mi)))
  83.                 mi = i;
  84.  
  85.         if(mi == -1)
  86.             break;
  87.  
  88.         if(cnt(mi) == INF)
  89.         {
  90.             del[mi] = 1;
  91.         }
  92.         else if(cnt(mi) == m)
  93.         {
  94.             ++q;
  95.  
  96.             int nw = (arr[mi] < n ? arr[arr[mi]] : INF);
  97.             for(int i = 0; i < n; ++i)
  98.                 if(arr[i] == arr[mi])
  99.                     arr[i] = nw;
  100.  
  101.             for(int i = mi; i < arr[mi]; ++i)
  102.                 del[i] = 1;
  103.             for(int i = 0; i < n; ++i)
  104.                 sum[i] = i ? sum[i-1] : 0 + (!del[i]);
  105.         }
  106.         else
  107.         {
  108.             printf("%d ", q);
  109.  
  110.             int id, j;
  111.             for(id = mi, j = 0; j < m; ++id)
  112.                 if(s[id] == p[j])
  113.                     ++j;
  114.                 else if(!del[id])
  115.                     break;
  116.             del[id] = true;
  117.             for(int i = 0; i < n; ++i)
  118.                 sum[i] = i ? sum[i-1] : 0 + (!del[i]);
  119.  
  120.             ++it;
  121.         }
  122.     }
  123.  
  124.     printf("%d ", mq);
  125.  
  126.     while(true)
  127.     {
  128.         int id = -1;
  129.         for(id = 0; id < n; ++id)
  130.             if(!del[id] && arr[id] != INF)
  131.                 break;
  132.         if(id == n) break;
  133.         del[id] = 1;
  134.         printf("%d ", mq);
  135.     }
  136.  
  137.     for(int i = mq-1; i >= 0; --i)
  138.         for(int j = 0; j < m; ++j)
  139.             printf("%d ", i);
  140.  
  141.     printf("\n");
  142.     return 0;
  143. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement