题目链接：http://codeforces.com/problemset/problem/427/D
大意是寻找两个字符串中最短的公共子串，要求子串在两个串中都是唯一的。
造一个S#T的串，做后缀数组，从小到大枚举子串长度在height数组中扫描，如果某一个组中来自两个串的数量分别为1，就找到了答案。
1 #include <iostream> 2 #include <vector> 3 #include <algorithm> 4 #include <string> 5 #include <string.h> 6 #include <stdio.h> 7 #include <math.h> 8 #include <stdlib.h> 9 #include <queue> 10 #include <stack> 11 #include <map> 12 #include <set> 13 #include <ctime> 14 #include <numeric> 15 #include <cassert> 16 17 using namespace std; 18 19 const int N=10005;; 20 21 char s[N]; 22 23 struct SuffixArray { 24 int wa[N], wb[N], cnt[N], wv[N]; 25 int rk[N], height[N]; 26 int sa[N]; 27 bool cmp(int r[], int a, int b, int l) { 28 return r[a] == r[b] && r[a+l] == r[b+l]; 29 } 30 void calcSA(char r[], int n, int m) { 31 int i, j, p, *x = wa, *y = wb; 32 for (i = 0; i < m; ++i) cnt[i] = 0; 33 for (i = 0; i < n; ++i) cnt[x[i]=r[i]]++; 34 for (i = 1; i < m; ++i) cnt[i] += cnt[i-1]; 35 for (i = n-1; i >= 0; --i) sa[--cnt[x[i]]] = i; 36 for (j = 1, p = 1; p < n; j *= 2, m = p) { 37 for (p = 0, i = n - j; i < n; ++i) y[p++] = i; 38 for (i = 0; i < n; ++i) if (sa[i] >= j) y[p++] = sa[i] - j; 39 for (i = 0; i < n; ++i) wv[i] = x[y[i]]; 40 for (i = 0; i < m; ++i) cnt[i] = 0; 41 for (i = 0; i < n; ++i) cnt[wv[i]]++; 42 for (i = 1; i < m; ++i) cnt[i] += cnt[i-1]; 43 for (i = n-1; i >= 0; --i) sa[--cnt[wv[i]]] = y[i]; 44 for (swap(x, y), p = 1, x[sa[0]] = 0, i = 1; i < n; ++i) 45 x[sa[i]] = cmp(y, sa[i-1], sa[i], j) ? p-1 : p++; 46 } 47 } 48 void calcHeight(char r[], int n) { 49 int i, j, k = 0; 50 for (i = 0; i <= n; ++i) rk[sa[i]] = i; 51 for (i = 0; i < n; height[rk[i++]] = k) 52 for (k?k--:0, j = sa[rk[i]-1]; r[i+k] == r[j+k]; k++); 53 } 54 bool solve(int k,int n,int div) { 55 int ca=0,cb=0; 56 for (int i=1;i<=n;i++) { 57 if (height[i]<k) { 58 if (ca==1&&cb==1) 59 return true; 60 ca=0;cb=0; 61 if (sa[i]<div) ca++; 62 else if (sa[i]>div) cb++; 63 continue; 64 } 65 if (sa[i]<div) ca++; 66 else if (sa[i]>div) cb++; 67 } 68 return ca==1&&cb==1; 69 } 70 }suf; 71 72 char a[N],b[N]; 73 74 int main(){ 75 scanf("%s %s",a,b); 76 int n=strlen(a),m=strlen(b); 77 strcpy(s,a); 78 s[n]='#'; 79 strcpy(s+n+1,b); 80 int tot=n+m+1; 81 suf.calcSA(s,tot+1,128); 82 suf.calcHeight(s,tot); 83 int ret=-1; 84 for (int i=1;i<=n;i++) { 85 if (suf.solve(i,tot,n)) { 86 ret=i; 87 break; 88 } 89 } 90 printf("%d ",ret); 91 return 0; 92 }