Life Forms
Mean:
给你n个串，让你找出出现次数大于n/2的最长公共子串。如果有多个，按字典序排列输出。
analyse:
经典题。
直接二分判断答案。
判断答案p时，我们扫一遍height数组，如果height[i]<p时开辟一个新段。
判断时用set存储所在串编号，不仅起到去重的作用，而且也起到统计段长的作用。
也可以直接用字符串hash来做，也是先二分，然后O(n)判断，时间复杂度和后缀数组一样。
Time complexity: O(N*logN)
Source code:
1.后缀数组:
/* * this code is made by crazyacking * Verdict: Accepted * Submission Date: 2015-09-05-14.44 * Time: 0MS * Memory: 137KB */ #include <queue> #include <cstdio> #include <set> #include <string> #include <stack> #include <cmath> #include <climits> #include <map> #include <cstdlib> #include <iostream> #include <vector> #include <algorithm> #include <cstring> using namespace std;
typedef long long(
LL);
typedef unsigned long long(
ULL);
const double eps(
1e-8);
const int MAXLEN = 200005;
struct Suffix { int s
[ MAXLEN ]; int sa [ MAXLEN ], t [ MAXLEN ], t2 [ MAXLEN ], c [ MAXLEN ], n;
int Rank [ MAXLEN ], height [ MAXLEN ]; void build_sa(
int m)
{ int i , * x = t , * y = t2;
for(
i = 0;
i < m;
i ++)
c [ i ] = 0;
for(
i = 0;
i < n;
i ++)
c [ x [ i ] = s
[ i ]] ++;
for(
i = 1;
i < m;
i ++)
c [ i ] += c [ i - 1 ]; for(
i = n
- 1;
i >= 0;
i --)
sa [ -- c [ x [ i ]]] = i;
for(
int k = 1;
k <= n;
k <<= 1)
{ int p
= 0;
for(
i = n
- k;
i < n;
i ++)
y [p
++ ] = i;
for(
i = 0;
i < n;
i ++)
if(
sa [ i ] >= k)
y [p
++ ] = sa [ i ] - k;
for(
i = 0;
i < m;
i ++)
c [ i ] = 0;
for(
i = 0;
i < n;
i ++)
c [ x [ y [ i ]]] ++;
for(
i = 0;
i < m;
i ++)
c [ i ] += c [ i - 1 ]; for(
i = n
- 1;
i >= 0;
i --)
sa [ -- c [ x [ y [ i ]]]] = y [ i ]; swap(
x , y);
p
= 1;
x [ sa [ 0 ]] = 0;
for(
i = 1;
i < n;
i ++)
x [ sa [ i ]] = y [ sa [ i - 1 ]] == y [ sa [ i ]] && y [ sa [ i - 1 ] + k ] == y [ sa [ i ] + k ] ? p
- 1 : p
++;
if(p
>= n)
break;
m = p;
} } void getHeight()
{ int i , j , k = 0;
for(
i = 0;
i < n;
i ++)
Rank [ sa [ i ]] = i;
for(
i = 0;
i < n;
i ++)
{ if(
k)
k --;
if(
Rank [ i ] == 0)
continue;
int j = sa [ Rank [ i ] - 1 ]; while(s
[ i + k ] == s
[ j + k ]) k ++;
height [ Rank [ i ]] = k;
} } } Suf;
const int N
= 1005;
int n
, l , r , id [ MAXLEN ]; char str [N
]; bool judge(
int x , int bo)
{ set < int > vis;
vis . insert(
id [ Suf . sa [ 1 ]]); for(
int i = 2;
i < Suf .n;
i ++)
{ while(
i < Suf .n
&& Suf . height [ i ] >= x)
{ vis . insert(
id [ Suf . sa [ i ]]); i ++;
} if(
vis . size()
* 2 > n)
{ if(
bo == 0)
return true;
for(
int j = 0;
j < x;
j ++)
printf(
"%c" , Suf .s
[ Suf . sa [ i - 1 ] + j ]); printf(
" \n ");
} vis . clear();
vis . insert(
id [ Suf . sa [ i ]]); } return false;
} void solve()
{ if(
! judge(
1 , 0))
{ printf(
"? \n ");
return;
} l = 1;
r ++;
while(
l < r)
{ int mid = (
l + r)
/ 2;
if(
judge(
mid , 0))
l = mid + 1;
else r = mid;
} l --;
judge(
l , 1);
} int main()
{ int bo = 0;
while(
~ scanf(
"%d" , &n)
&& n)
{ if(
bo)
printf(
" \n ");
else bo = 1;
if(n
== 1)
{ scanf(
"%s" , str);
printf(
"%s \n " , str);
continue;
} int tot = 0;
r = 0;
for(
int i = 0;
i < n;
i ++)
{ scanf(
"%s" , str);
int len = strlen(
str);
r = max(
len , r);
for(
int j = 0;
j < len;
j ++)
{ id [ tot ] = i;
Suf .s
[ tot ++ ] = str [ j ]; } id [ tot ] = i;
Suf .s
[ tot ++ ] = 'z' + i + 1;
} Suf .n
= tot;
Suf . build_sa(
'z' + n
+ 1);
Suf . getHeight();
solve();
} return 0;
} 2.字符串hash:
/* * this code is made by crazyacking * Verdict: Accepted * Submission Date: 2015-09-03-12.21 * Time: 0MS * Memory: 137KB */ #include <queue> #include <cstdio> #include <set> #include <string> #include <stack> #include <cmath> #include <climits> #include <map> #include <cstdlib> #include <iostream> #include <vector> #include <algorithm> #include <cstring> using namespace std;
typedef long long(
LL);
typedef unsigned long long(
ULL);
const double eps(
1e-8);
const int MAXN = 10001010 , seed = 173;
int n
, id [ MAXN ]; char s
[ MAXN ], str [ 5010 ]; vector < pair < int , int > > same;
int getBegin(
int st , int en)
{ for(
int i = 0;
i < same . size();
++ i)
if(
st >=((
& same [ i ]) -> first)
&& en <=((
& same [ i ]) -> second))
return (
& same [ i ]) -> first;
return - 1;
} vector < string > ans;
bool judge(
int p
, bool ty)
{ vector < pair < ULL , pair < int , int > > > v;
ULL hv = 0 , base = 1;
for(
int i = 0;
i <p;
++ i)
{ hv = hv * seed +s
[ i ]; base *= seed;
} v . push_back(
make_pair(
hv , make_pair(
0 ,p
- 1)));
int len = strlen(s);
for(
int i =p;
i < len;
++ i)
{ hv = hv * seed +s
[ i ] - base *s
[ i -p
]; if(
getBegin(
i -p
+ 1 , i)
!=- 1)
v . push_back(
make_pair(
hv , make_pair(
i -p
+ 1 , i)));
} sort(
v . begin (), v . end());
set < int > id;
int st , en , cnt;
bool f = false;
ans . clear();
auto p1 = v . begin (), p2 = v . begin();
++ p2;
for(;
p2 != v . end();
++ p1 , ++ p2)
{ if(
p2 -> first != p1 -> first)
id . clear();
else { while(
p2 -> first == p1 -> first)
{ st =(
& p2 -> second)
-> first;
en =(
& p2 -> second)
-> second;
if(
getBegin(
st , en)
!=- 1 && getBegin((
& p1 -> second)
-> first ,( & p1 -> second)
-> second)
!=- 1 && id . find(
getBegin(
st , en))
== id . end()
&& getBegin((
& p1 -> second)
-> first ,( & p1 -> second)
-> second)
!= getBegin(
st , en))
{ id . insert(
getBegin(
st , en));
} ++ p1 , ++ p2;
} -- p1 , -- p2;
if((
id . size()
+ 1)
* 2 >n)
{ f = true;
st =(
& p2 -> second)
-> first;
en =(
& p2 -> second)
-> second;
cnt = 0;
for(
int i = st;
i <= en;
++ i)
str [ cnt ++ ] =s
[ i ]; str [ cnt ] = '\0';
ans . push_back(
str);
id . clear();
} } } if(
! ty)
return f;
sort(
ans . begin (), ans . end());
for(
int i = 0;
i < ans . size();
++ i)
printf(
"%s \n " , ans [ i ]. c_str());
} int main()
{ int Cas = 0;
while(
~ scanf(
"%d" , &n)
&& n)
{ if(
Cas ++)
puts(
"");
if(n
== 1)
{ scanf(
"%s" ,s);
puts(s);
continue;
} same . clear();
int maxLen = 0 , st , en;
memset(s
, 0 , sizeof s);
for(
int i = 0;
i <n;
++ i)
{ scanf(
"%s" , str);
st = strlen(s);
maxLen = max(
maxLen ,( int)
strlen(
str));
strcat(s
, str);
en = strlen(s);
same . push_back(
make_pair(
st , en - 1));
} if(
! judge(
1 , 0))
{ puts(
"?");
continue;
} int l = 1 , r = maxLen , mid;
while(
r > l + 1)
{ mid = l +(
r - l)
/ 2;
if(
judge(
mid , 0))
l = mid;
else r = mid;
} judge(
l , 1);
} return 0;
} /* */