[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':' ');
}