2016年3月10日 星期四

[TIOJ 1725][Z algorithm] Massacre at Camp Happy

原題連結
先了解一個問題:給定字串A,B,長度皆為n,要如何線性判定A和B是否只差1個字元呢?



等等,這不是很簡單嗎,直接掃過去就好啦!O(n)!

那麼這題的難點來了:字串是環狀的,如果每個起點都掃過一次的話,O(n)個字串每個都掃O(n)次會變成O(n^2)!

那麼,將思緒放回經典字串算法上面:給定字串A,B,長度皆為n,要如何藉由Z algorithm或是KMP判定A和B是否只差1個字元呢?
以下給出利用Z value的想法。

令A=aabaab B=aaaaab,他們只差1個字元,我們不妨將A拆成三段來看:
A= aa + b + aab ,第一段和第三段是成功匹配的字串,第二段只有單一一字元是匹配失敗的字元。
接下來的思考有點吃經驗。這其實告訴我們一件事情: 字串長度=A和B共同最長前綴長度 + 1 + rev(A)和rev(B)的共同最長前綴長度!(rev:reverse)

那麼算法過程就很明顯了,求出字串"B$AA"的Z value和"rev(B)$rev(AA)"的Z value,枚舉座標計算上面的式子是否成立,就可以達到時間複雜度線性了。

細節上,座標點的位置不要算錯,建議拿筆真的寫下來......

#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const int maxn=1000000+5;
void getZ(char* s,int* Z)
{
    int n=strlen(s),farest=0;
    Z[0]=0;
    for(int i=1;i<n;i++)
    {
        Z[i]=0;
        if(farest+Z[farest]>=i)
        {
            int ip=i-farest;
            if(ip+Z[ip]<Z[farest]) Z[i]=Z[ip];
            else Z[i]=farest+Z[farest]-i;
        }
        while(i+Z[i]<n && s[i+Z[i]]==s[Z[i]]) Z[i]++;
        if(i+Z[i]>farest+Z[farest]) farest=i;
    }
}
char A[maxn],B[maxn*3];
int Z[maxn*3],ZR[maxn*3];
int main()
{
    int n;
    scanf("%d%s%s",&n,A,B);
    B[n]='$';
    for(int i=0;i<n;i++) B[i+n+1]=A[i];
    for(int i=0;i<n;i++) B[i+2*n+1]=A[i];
    B[3*n+1]='\0';
    getZ(B,Z);
    reverse(B,B+n);reverse(B+n+1,B+3*n+1);
    getZ(B,ZR);
    vector<int> ans;
    for(int i=n+1;i<2*n+1;i++) if(Z[i]+ZR[2*n-1-(i-n-1+n-1)+n+1]+1==n) ans.push_back(i-n-1);
    if(!ans.size()) {printf("NIE\n");return 0;}
    printf("TAK\n");
    for(int i=0;i<ans.size();i++) printf("%d%c",ans[i],i==ans.size()-1?'\n':' ');
}

沒有留言:

張貼留言