HDU2328 Corporate Identity

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

#include <iostream>
#include <cstring>
#include <cstdio>
#include <set>
 
using namespace std;

const int N = 800010, M = 4010;

int n, T;
int sa[N], rk[N], cnt[N], oldrk[N << 1], id[N], px[N];
char s[N];
int ht[N];
int belong[N], idx;
int maxr = N;

inline bool cmp(int x, int y, int k) {
    return oldrk[x] == oldrk[y] && oldrk[x + k] == oldrk[y + k];
}

void SA() {
	int i, p = 0, k, m = 300;
	memset(cnt, 0, sizeof cnt);
	for (i = 1; i <= n; i++) cnt[rk[i] = s[i]]++;
	for (i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
	for (i = n; i >= 1; i--) sa[cnt[rk[i]]--] = i;
	for (k = 1; k < n; k <<= 1, m = p) { 
		for (p = 0, i = n ; i > n - k; i--) id[++p] = i;
		for (i = 1;i <= n; i++){
			if (sa[i] > k) id[++p] = sa[i] - k;
		}
		memset(cnt, 0, sizeof cnt);
		for (i = 1; i <= n; i++) cnt[px[i] = rk[id[i]]]++;
		for (i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
		for (i = n; i >= 1; i--) sa[cnt[px[i]]--] = id[i];
		memcpy(oldrk, rk, sizeof rk);
		for (p = 0, i = 1; i <= n; i++){
			rk[sa[i]] = cmp(sa[i], sa[i - 1], k) ? p : ++p;
		}
	}
	for (int i = 1; i <= n; i++) {
		if (rk[i] == 1) continue;
		int k = max(ht[rk[i - 1]] - 1, 0);
		while (i + k <= n && s[i + k]== s[sa[rk[i] - 1] + k]) k++;
		ht[rk[i]] = k;
	}
}

bool check(int len) {
    set<int> S;
    S.insert(belong[sa[1]]);
    for (int i = 2; i <= n; i++) {
        while (ht[i] >= len && i <= n) {
            S.insert(belong[sa[i]]);
            i++;
        }
        if (S.size() == T) return true;
        S.clear();
        S.insert(belong[sa[i]]);
    }
    return false;
}

void print(int len) {
    set<int> S;
    bool flag = false;
    S.insert(belong[sa[1]]);
    for (int i = 2; i <= n; i++) {
        while (ht[i] >= len && i <= n) {
            S.insert(belong[sa[i]]);
            i++;
        }
        if (S.size() == T) {
            for (int j = sa[i - 1]; j <= sa[i - 1] + len - 1; j++) putchar(s[j]);
            puts("");
            flag = true;
            break;
        }
        S.clear();
        S.insert(belong[sa[i]]);
    }
    if (!flag) puts("IDENTITY LOST");
}

void solve() {
    maxr = N;
    char a = 1;
    memset(belong, -1, sizeof belong);
    idx = 0;
    int t = 0;
    for (int i = 0; i < T; i++) {
        scanf("%s", s + t + 1);
        int m = strlen(s + 1);
        maxr = min(maxr, m - t);
        s[m + 1] = a++;
        if (a == 97) a = 1;
        for (int j = t + 1; s[j]; j++) belong[j] = i;
        t = m + 1;
    }
    s[t] = '\0';
    // printf("%s\n", s + 1);
    // for (int i = 1; s[i]; i++) printf("%d ", belong[i]);
    n = strlen(s + 1);
    SA();
    // 二分LCP的长度
    int l = 1, r = maxr;
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    print(l);
}

int main() {
    while (scanf("%d", &T), T) solve();
    return 0;
}