ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1713. Key Substrings

WA3
Posted by pizdec 15 Aug 2018 14:22
I use suffix array but WA3.
Give me some tests.

#include <string>
#include <iostream>
using namespace std;

int min(int x, int y) { return x < y ? x : y; }
int max(int x, int y) { return x > y ? x : y; }
int Min(int l, int r);

const int nmax = 1005;
const int maxlen = 1000 * 105;
const int alphabet = 256;

int n, m, sum;
int p[maxlen], cnt[maxlen], c[maxlen];
int pn[maxlen], cn[maxlen], lcp[maxlen];
int who[maxlen], up[maxlen], down[maxlen], a[nmax], b[nmax];
int ans_len[nmax], ans_ind[nmax];
string s, str[nmax];

int main()
{
cin>>m;
for(int i=0;i<m;i++) cin>>str[i], s+=str[i];
m++;
str[m-1]="#";
s+=str[m-1];

n = s.length();

memset(cnt, 0, alphabet * sizeof(int));
for (int i = 0; i<n; ++i) ++cnt[s[i]];
for (int i = 1; i<alphabet; ++i) cnt[i] += cnt[i - 1];
for (int i = 0; i<n; ++i) p[--cnt[s[i]]] = i;
c[p[0]] = 0;
int classes = 1;
for (int i = 1; i<n; ++i)
{
if (s[p[i]] != s[p[i - 1]])  ++classes;
c[p[i]] = classes - 1;
}

for (int h = 0; (1 << h)<n; ++h)
{
for (int i = 0; i<n; ++i)
{
pn[i] = p[i] - (1 << h);
if (pn[i] < 0)  pn[i] += n;
}
memset(cnt, 0, classes * sizeof(int));
for (int i = 0; i<n; ++i) ++cnt[c[pn[i]]];
for (int i = 1; i<classes; ++i) cnt[i] += cnt[i - 1];
for (int i = n - 1; i >= 0; --i) p[--cnt[c[pn[i]]]] = pn[i];
cn[p[0]] = 0;
classes = 1;
for (int i = 1; i<n; ++i)
{
int mid1 = (p[i] + (1 << h)) % n, mid2 = (p[i - 1] + (1 << h)) % n;
if (c[p[i]] != c[p[i - 1]] || c[mid1] != c[mid2]) ++classes;
cn[p[i]] = classes - 1;
}
memcpy(c, cn, n * sizeof(int));
}

n--, m--, s.erase(n, 1);
for (int i = 0; i < n; i++) p[i] = p[i + 1];

sum = 0;
for (int i = 0; i < m; i++) a[i]=sum, b[i]=sum+str[i].length()-1, sum += str[i].length();

for (int i = 0; i < n; i++)
{
int j = 0;
while (!(a[j] <= p[i] && p[i] <= b[j])) j++;
who[i] = j;
}

for (int i = 0; i <= n - 2; i++)
{
lcp[i] = 0;
int hr = max(p[i], p[i+1]);
int gr = min(b[who[i]]-p[i]+1, b[who[i+1]]-p[i+1]+1);
while (hr+lcp[i]<n && lcp[i]<gr && s[p[i] + lcp[i]] == s[p[i + 1] + lcp[i]]) lcp[i]++;
}

down[0] = -1;
for (int i = 1; i < n; i++) down[i] = who[i - 1] == who[i]? down[i - 1] : i - 1;

up[n - 1] = -1;
for (int i = n - 2; i >= 0; i--) up[i] = who[i + 1] == who[i] ? up[i + 1] : i + 1;

for (int i = 0; i < m; i++) ans_len[i] = str[i].length(), ans_ind[i]=a[i];

for (int i = 0; i < n; i++)
{
int val1 = down[i] == -1 ? 0 : Min(down[i], i - 1);
int val2 = up[i] == -1 ? 0 : Min(i, up[i]-1);
int now_len = max(val1, val2) + 1;
if (now_len<=b[who[i]]-p[i]+1 && ans_len[who[i]] > now_len) ans_len[who[i]] = now_len, ans_ind[who[i]] = p[i];
}

for (int i = 0; i < m; i++)
{
for (int j = 0; j < ans_len[i]; j++) cout << s[ans_ind[i] + j];
if(i+1<m) cout << endl;
}

return 0;
}

int Min(int l, int r)
{
int res=maxlen+5;
for(int i=l;i<=r;i++) res=min(res, lcp[i]);
return res;
}

Edited by author 16.08.2018 00:42