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