ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
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