|
|
вернуться в форумWrong answer 2... Please help (Code in here) #include <iostream> #include <string> #include <algorithm> using namespace std; string a; int k; int array[9096], n, bucket[9096], lbucket[9096], h = 0; void scan(){ cin >> k >> a; a += a.substr(0, k - 1); n = a.size(); } bool f(int x, int y){ if ( !h ) return a[x] < a[y]; if ( bucket[x] < bucket[y] ) return 1; if ( bucket[y] < bucket[x] ) return 0; int bx, by; if ( x + h >= n ) bx = n - (x + h) - 1; else bx = bucket[x + h]; if ( y + h >= n ) by = n - (y + h) - 1; else by = bucket[y + h]; return bx < by; } bool makebuckets(){ int br = 0; for ( int i = 0; i < n; ++i ){ if ( i > 0 ) if ( f(array[i], array[i - 1]) || f(array[i - 1], array[i]) ) ++br; lbucket[array[i]] = br; } for ( int i = 0; i < n; ++i ) bucket[i] = lbucket[i]; ++br; return (br == n); } void buildsuffixarray(){ for ( int i = 0; i < n; ++i ) array[i] = i; sort (array, array + n, f); if ( makebuckets() ) return; for ( h = 1;; h *= 2 ){ sort(array, array + n, f); if ( makebuckets() ) break; } } int findnext(int st, int i){ ++i; for (i; i < n; ++i) if ( array[i] >= st && array[i] < st + k ) return i; return -1; } int rez(int t){ int p = findnext(t, -1), d, result = (k + 1) * k / 2; d = findnext(t, p); int br = 0; while ( d > 0 ){ int j = 0; while ( a[array[p] + j] == a[array[d] + j] && array[p] + j < t + k && array[d] + j < t + k ) ++j; result -= j; p = d; d = findnext(t, d); ++br; } if ( br != k - 1 ) while(1); return result; } void solve(){ buildsuffixarray(); cout << rez(0); for ( int i = 1; i < n - k + 1; ++i ) cout << " " << rez(i); cout << endl; } int main(){ scan(); solve(); } I am getting mad... no idea where my code is wrong... The idea is right |
|
|