[HOJ 128] Matching

作法：

我們一樣往KMP的方向想，首先我們會需要 fail 函數，回顧他的定義，$fail[i]$代表說「當已經匹配好$1,...,i$時，如果$i+1$失配，那麼要轉換成已經匹配好$1,...,fail[i]$的情形」，而這裡的匹配的定義根一般字串匹配不一樣，是要兩個子序列的「相對大小關係」一樣時則叫作匹配。因此回顧我們在算 fail 函數時的方法，假設當前要決定$i$的 fail 值，令$fail[i-1]=j$，那麼首先我們要判斷「$1,...,i$的長度為$j+1$的後綴」是否和「長度$j+1$的前綴」匹配（再次強調這裡匹配的定義不一樣），而這等價於：「在$x[i-j],...,x[i-1]$之中比$x[i]$小的數的個數」等於「在$x[1],...,x[j]$中比$x[j+1]$小的數的個數」，其中$x$為要求$fail$函數的陣列。因此就可以維護一個 BIT 來查詢所求的答案（因為會支援加數字和刪數字）。如果發現失配了就一樣沿著 fail 往回跳，直到長度變$0$或是匹配成功為止。由這裡就可以發現，其實 fail 函數建立的過程幾乎一樣，只是變成要多維護兩個 BIT ，並用 BIT 來查詢是否匹配成功而已。在和原數列匹配的過程也一模一樣（本來在原本的寫法中建 fail 函數和匹配的過程的程式碼就幾乎一樣了），失配就沿 fail 往前跳，維護好兩個 BIT 即可。最後要記得當找到一個地方成功匹配了模版串時也要沿 fail 往前跳，跟原本的 KMP 一樣。


code :

#include<bits/stdc++.h>
#define lowbit(x) ((x)&(-x))
using namespace std;
const int maxn=1000000+10 ;
 
int bit[2][maxn] ;
void add(int id,int x,int val)
{
    for(;x<maxn;x+=lowbit(x)) bit[id][x]+=val ;
}
int query(int id,int x)
{
    int ret=0 ;
    for(;x;x-=lowbit(x)) ret+=bit[id][x] ;
    return ret ;
}
 
int a[maxn],b[maxn],fail[maxn] ;
vector<int> v,ans ;
main()
{
    int n,m ; scanf("%d%d",&m,&n) ;
    for(int i=1;i<=m;i++)
    {
        int x ; scanf("%d",&x) ;
        b[x]=i ;
    }
    for(int i=1;i<=n;i++) scanf("%d",&a[i]) , v.push_back(a[i]) ;
    sort(v.begin(),v.end()) ;
    for(int i=1;i<=n;i++) a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1 ;
    for(int i=2,j=0;i<=m;i++)
    {
        while(j && query(0,b[j+1]-1)!=query(1,b[i]-1))
        {
            int j2=fail[j] ;
            for(;j!=j2;j--)
                add(0,b[j],-1) , add(1,b[i-j],-1) ;
        }
        if(query(0,b[j+1]-1)==query(1,b[i]-1))
            j++ , add(0,b[j],1) , add(1,b[i],1) ;
        fail[i]=j ;
    }
    memset(bit,0,sizeof(bit)) ;
    for(int i=1,j=0;i<=n;i++)
    {
        while(j && query(0,b[j+1]-1)!=query(1,a[i]-1))
        {
            int j2=fail[j] ;
            for(;j!=j2;j--)
                add(0,b[j],-1) , add(1,a[i-j],-1) ;
        }
        if(query(0,b[j+1]-1)==query(1,a[i]-1))
            j++ , add(0,b[j],1) , add(1,a[i],1) ;
        if(j==m)
        {
            ans.push_back(i-j+1) ;
            int j2=fail[j] ;
            for(;j!=j2;j--)
                add(0,b[j],-1) , add(1,a[i-j+1],-1) ;
        }
    }
    printf("%d\n",ans.size()) ;
    for(int i=0;i<ans.size();i++) printf("%d%c",ans[i],i+1==ans.size()?'\n':' ') ;
}