Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <cmath>
- #include <vector>
- #include <algorithm>
- #include <cstring>
- #include <string>
- #include <set>
- #include <map>
- using namespace std;
- char s[2005], p[505];
- int n, m, q = 0, mq = 0;
- const int INF = 100005;
- int arr[2005];
- int sum[2005];
- bool del[2005];
- bool usd[2005];
- int cnt(int id)
- {
- if(arr[id] > n)
- return INF;
- int rsum = sum[arr[id]-1];
- int lsum = id ? sum[id-1] : 0;
- return rsum - lsum;
- }
- int main() {
- scanf("%s%s", s, p);
- n = strlen(s);
- m = strlen(p);
- for(int i = 0; i < n; ++i)
- {
- int j = i, id = 0;
- for(; j < n && id < m; ++j)
- {
- if(s[j] == p[id])
- ++id;
- }
- arr[i] = (id == m ? j : INF);
- }
- for(int i = 0; i < n; ++i)
- sum[i] = (i ? sum[i-1] : 0) + (!del[i]);
- for(int i = 0; i < n; )
- {
- if(arr[i] != INF) ++mq;
- i = arr[i];
- }
- int it = 0;
- while(q < mq)
- {
- /*cout << "ARR\n";
- for(int i = 0; i < n; ++i)
- cout << arr[i] << " ";
- cout << endl;
- cout << "DEL\n";
- for(int i = 0; i < n; ++i)
- cout << del[i] << " ";
- cout << endl;
- cout << "SUM\n";
- for(int i = 0; i < n; ++i)
- cout << sum[i] << " ";
- cout << endl;
- cout << "CNT\n";
- for(int i = 0; i < n; ++i)
- cout << cnt(i) << " ";
- cout << endl;
- fflush(stdout);*/
- int mi = -1;
- for(int i = 0; i < n; ++i)
- if(mi == -1 || (!del[i] && cnt(i) < cnt(mi)))
- mi = i;
- if(mi == -1)
- break;
- if(cnt(mi) == INF)
- {
- del[mi] = 1;
- }
- else if(cnt(mi) == m)
- {
- ++q;
- int nw = (arr[mi] < n ? arr[arr[mi]] : INF);
- for(int i = 0; i < n; ++i)
- if(arr[i] == arr[mi])
- arr[i] = nw;
- for(int i = mi; i < arr[mi]; ++i)
- del[i] = 1;
- for(int i = 0; i < n; ++i)
- sum[i] = i ? sum[i-1] : 0 + (!del[i]);
- }
- else
- {
- printf("%d ", q);
- int id, j;
- for(id = mi, j = 0; j < m; ++id)
- if(s[id] == p[j])
- ++j;
- else if(!del[id])
- break;
- del[id] = true;
- for(int i = 0; i < n; ++i)
- sum[i] = i ? sum[i-1] : 0 + (!del[i]);
- ++it;
- }
- }
- printf("%d ", mq);
- while(true)
- {
- int id = -1;
- for(id = 0; id < n; ++id)
- if(!del[id] && arr[id] != INF)
- break;
- if(id == n) break;
- del[id] = 1;
- printf("%d ", mq);
- }
- for(int i = mq-1; i >= 0; --i)
- for(int j = 0; j < m; ++j)
- printf("%d ", i);
- printf("\n");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement