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;

}

巴特西

CF427D

CF427D

题意：

解析：

CODE:

最新文章

热门文章