POJ 3450 - Corporate Identity

http://poj.org/problem?id=3450

概要

\(N\) 個の文字列が与えられるので、すべての文字列の連続した部分文字列で長さが最大であるものを答える。 複数存在する場合は辞書式順序で最小のものを答える。 そのような連続した部分文字列が存在しない場合は「IDENTITY LOST」と答える。

制約

解法

Suffix Array を構築し、最初の文字列の各 Suffix Array について、それ以外の文字列と何文字マッチするかを調べる。

\(L\) はそんなに大きくないので、普通にソートして \(O(L ^ 2 \log L\)) で \(N\) 個の Suffix Array を構築しても間に合う。 とはいえ string をコピーしまくるようなコードでは TLE したので配列で書き直して 329MS で通した。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 static const int MAXN = 4000;
 6 static const int MAXLEN = 200;
 7 
 8 struct build_less
 9 {
10   const char *s;
11   build_less(const char *a) : s(a) {}
12   bool operator()(int i, int j) const { return strcmp(s+i, s+j) < 0; }
13 };
14 
15 struct search_less
16 {
17   const char *s;
18   int idx;
19   search_less(const char *t, int i) : s(t), idx(i) {}
20   bool operator()(int i, char c) const { return s[i+idx] < c; }
21   bool operator()(char c, int i) const { return c < s[i+idx]; }
22 };
23 
24 struct SuffixArray
25 {
26   char s[MAXLEN+1];
27   int a[MAXLEN+1];;
28   int len;
29 
30   void build()
31   {
32     for (int i = 0; i < len; i++) {
33       a[i] = i;
34     }
35     sort(a, a+len, build_less(s));
36   }
37 
38   int search(const char *t) const
39   {
40     typedef const int *Iterator;
41     Iterator first = a, last = a+len;
42     int i;
43     for (i = 0; t[i] != '\0'; i++) {
44       const pair<Iterator, Iterator> r = equal_range(first, last, t[i], search_less(s, i));
45       first = r.first;
46       last = r.second;
47       if (first == last) {
48         return i;
49       }
50     }
51     return i;
52   }
53 };
54 
55 
56 int main()
57 {
58   int N;
59   while (scanf("%d", &N) != EOF && N != 0) {
60     static SuffixArray sa[MAXN];
61     for (int i = 0; i < N; i++) {
62       scanf("%s", sa[i].s);
63       sa[i].len = strlen(sa[i].s);
64       sa[i].build();
65     }
66     char *t = sa[0].s;
67     const int tlen = sa[0].len;
68 
69     char *ans = 0;
70     int anslen = -1;
71     for (int i = 0; t[i] != '\0'; i++) {
72       char *u = t+i;
73       int n = tlen-i;
74       for (int j = 1; j < N; j++) {
75         n = min(n, sa[j].search(u));
76       }
77       if (n > anslen
78           || (n == anslen && strcmp(u, ans) < 0)) {
79         ans = u;
80         anslen = n;
81       }
82     }
83     if (anslen == 0) {
84       puts("IDENTITY LOST");
85     } else {
86       ans[anslen] = 0;
87       puts(ans);
88     }
89   }
90   return 0;
91 }
poj/3450.cc