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