[CF 533F] Encoding

作法：

考慮一個這兩個字串可以成功匹配的位置，當我們只看 S 中的特定一個字母時，假設是 X 好了，那麼在所有 X 出現的位置裡，對應到 T 中一定全部都視同一個字母，假設他為 Y 好了，那麼這同時也代表 Y 在 T 中出現的位置恰好就是對應的 X 在 S 中出現的位置。因此我們可以反過來作：枚舉字母 X 和字母 Y ，看看 T 可以被擺在 S 的哪個地方，使得所有的 T 中的 Y 所對應到的 S 上的字母都是 X ，並且不會有少對應的情況（也就是在被 T 蓋住的這個區間內的 S 中的所有 X 恰好和出現在 T 中的所有 Y 對應到），再來一樣考慮可以成功匹配的位置，假設為 p 好了（也就是把 T 的第一個字母放在 S 的第 p 個字母時可以成功匹配），那麼所有在 S 中這個區間內的所有字母都一定會配對到另一個字母，因此我們對每個位置都紀錄「把 T 放在這裡時有幾個字母成功匹配了」，具體來說是：當我們發現 S 中的 X 和 T 中的 Y 會在把 T 放在 q 位置的時候成功匹配的話，就把 q 位置的成功匹配值加上「 T 中 Y 的個數」，那麼就會得到匹配成功的 p 位置的成功匹配值一定會等於 T 的長度。因此首先可以把一些不可能是答案的位置篩掉。再來要確認的是，把 T 放在 S 的那個位置時，他們之間的字母的對應關係是否和題目要求的相同，而這只要在前面處理「 T 中的 Y 和 S 中的 X 在哪些位置匹配」時，再對所有找到的位置紀錄「此時 X 會被對應到 Y」，就可以確認這樣的對應關係是否為題目要求的了。

最後，在處理「 T 中的 Y 和 S 中的 X 在哪些位置匹配」的時候，一種方法是當確定 X 和 Y 時，把 S 中所有的 X 都視為 1 ，其他則視為0，而 T 中則是所有的 Y 都視為 1 ，其他視為0，把兩個字串拿去做 KMP ，這樣單次的時間會是 O( |S| + |T| ) 。或是另一種方法是：把所有 X 出現在 S 中的位置都丟進一個 vector 裡面， Y 出現在 T 中的位置丟進另一個 vector 裡面，然後把兩個 vector 分別差分，再拿去匹配第二個序列出現在第一個序列的哪裡。這樣的複雜度會是 O( S中X的個數 + T中Y的個數 ) 。如果仔細算一下會發現前者的總複雜度會是 26 * 26 *( |S| + |T| )，後者則是 26 *( |S| + |T| )。兩種方法都會過，我寫的是第2種方法，他比第1種難寫很多QQ ，是之後我看詳解才知道有第1種作法的。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10 ;
 
int fail[maxn] ;
void getfail(const vector<int> &v)
{
    if(v.size()==1) return ;
    fail[0]=-1 ;
    for(int i=1,j=-1;i+1<v.size();i++)
    {
        while(j>=0 && v[j+2]-v[j+1]!=v[i+1]-v[i])
            j=fail[j] ;
        if(v[j+2]-v[j+1]==v[i+1]-v[i]) j++ ;
        fail[i]=j ;
    }
}
 
void match(const vector<int> &v,const vector<int> &S,vector<int> &ret)
{
    ret.clear() ;
    int sz=v.size() , last=v[sz-1] ;
    if(sz==1)
    {
        for(auto i : S) ret.push_back(i-last+1) ;
        return ;
    }
    for(int i=0,j=-1;i+1<S.size();i++)
    {
        while(j>=0 && v[j+2]-v[j+1]!=S[i+1]-S[i]) j=fail[j] ;
        if(v[j+2]-v[j+1]==S[i+1]-S[i]) j++ ;
        if(j==sz-2) ret.push_back(S[i+1]-last+1) , j=fail[j] ;
    }
}
 
vector<int> v1[30],v2[30] ;
 
int mch[maxn][30],num[maxn] ;
void update(int pos,int sz,int i,int j)
{
    num[pos]+=sz ;
    mch[pos][i]=j ;
}
 
vector<int> tmp,ans ;
char s[maxn],t[maxn] ;
main()
{
    int n,m ; scanf("%d%d%s%s",&n,&m,s+1,t+1) ;
    for(int i=1;i<=n;i++) v1[s[i]-'a'+1].push_back(i) ;
    for(int i=1;i<=m;i++) v2[t[i]-'a'+1].push_back(i) ;
    for(int i=1;i<=26;i++) if(!v2[i].empty())
    {
        getfail(v2[i]) ;
        int sz=v2[i].size() ;
        for(int j=1;j<=26;j++) if(!v1[j].empty())
        {
            match(v2[i],v1[j],tmp) ;
            for(auto it : tmp) if(it>=1 && it<=n-m+1)
                update(it,sz,i,j) ;
        }
    }
    for(int i=1;i<=n-m+1;i++) if(num[i]==m)
    {
        bool ok=1 ;
        for(int j=1;j<=26;j++) if(mch[i][j])
        {
            int x=mch[i][j] ;
            if(mch[i][x] && mch[i][x]!=j)
                {ok=0 ; break ;}
            mch[i][x]=j ;
        }
        if(ok) ans.push_back(i) ;
    }
    printf("%d\n",ans.size()) ;
    for(int i=0;i<ans.size();i++) printf("%d%c",ans[i],i+1==ans.size()?'\n':' ') ;
}