CF427D

素颜马尾好姑娘i 2024-04-20 10:25 89阅读 0赞

##  ##

CF427D

> SA的奇技淫巧，其实就是板子。

### 题意： ###

> 给定两个字符串，求最短的满足各只出现一次的连续公共字串

### 解析： ###

> 一般情况下，SA都是用来求最长公共前缀的，好像和这道题所求的最短公共子串没有任何关系。  
> 但我们依然可以通过类比思路得出：
> 
> > 想一想为什么要寻找zz最大的元素？  
> > 因为如果小于最大值，那么最大值就会包含这个序列。  
> > 所以答案就是，一个元素，没有z值比这个元素大的，自然就是要选z的最大值  
> > 从上述思路，寻找如何让答案尽量小  
> > z的次大值自然是不行的，但是发现次大值+1是满足条件的  
> > 一方面，它比最大值小，所以被唯一的最大值包含；另一方面，它比次大值大，所以仅被最大值包含  
> > 所以可证，次大值+1也是唯一的。  
> > 所以，按如上方法，对 $ S\_1 $ 的每一个后缀求最大值和次大值，再用次大值更新答案  
> > 然后我们就能愉快的用SA解决这个问题了。

### CODE: ###

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; #define LL long long #define N 10010 string s1,s2,str; int SA[N],rk[N],tp[N],cnt[N]; int len,tot,m,a[N],height[N]; void qsort() { for(int i = 1 ; i <= m ; i++) cnt[i] = 0; for(int i = 1 ; i <= tot; i++) cnt[rk[i]]++; for(int i = 1 ; i <= m ; i++) cnt[i] += cnt[i - 1]; for(int i = tot ; i >= 1 ; i--) SA[cnt[rk[tp[i]]]--] = tp[i]; } inline bool cmp(int *f,int x,int y,int w) { return f[x] == f[y] && f[x + w] == f[y + w]; } void build_SA() { m = 127; for(int i = 1 ; i <= tot ; i++) { rk[i] = a[i]; tp[i] = i; } qsort(); for(int w = 1 , p = 0 ; p < tot ; w += w,m = p) { p = 0; for(int i = tot - w + 1 ; i <= tot ; i++) tp[++p] = i; for(int i = 1 ; i <= tot ; i++) { if(SA[i] > w) tp[++p] = SA[i] - w; } qsort(); swap(rk,tp); rk[SA[1]] = p = 1; for(int i = 2 ; i <= tot ; i++) rk[SA[i]] = cmp(tp,SA[i],SA[i - 1],w) ? p : ++p; } int j = 0, k = 0; for(int i = 1 ; i <= tot ; height[rk[i++]] = k) { for(k = k ? k - 1 : k, j = SA[rk[i] - 1] ; a[i + k] == a[j + k] ; k++); } } inline bool check(int k,int div) { int cnt1 = 0,cnt2 = 0; for(int i = 1 ; i <= tot ; i++) { if(height[i] < k) { if(cnt1 == 1 && cnt2 == 1) return true; cnt1 = cnt2 = 0; if(SA[i] <= div) cnt1++; else if(SA[i] >= div) cnt2++; continue; } if(SA[i] <= div) cnt1++; else if(SA[i] >= div) cnt2++; } return cnt1 == 1 && cnt2 == 1; } int main() { cin>>s1>>s2; len = s1.length(); str = s1 + '#' + s2;//加入'#'表示两个字符串的分界点。 tot = len + s2.length() + 1; for(int i = 1 ; i <= tot ; i++) a[i] = str[i - 1]; build_SA(); int ans = -1; for(int i = 1 ; i <= len ; i++) { if(check(i,len)) { ans = i; break; } } printf("%d \n",ans); //system("pause"); return 0; }

转载于:https://www.cnblogs.com/Repulser/p/11373550.html