給定一個$1\sim n$的排列$p_i$和長為$m$的序列$h_i$，求$h$有多少個字串匹配$p$。$A$匹配$p$指：$A,p$等長且將$A$從小到大排序后，依次為$A_{p_1},A_{p_2},...,A_{p_n}$。 $n,m\leq 10^6$。

洛谷
LOJ

太晚做題果然不行，老是忘了題意看了三晚上，wtcl。
不愧是退役后第一道純OI題

---

\(Description\)
給定一個\(1\sim n\)的排列\(p_i\)和長為\(m\)的序列\(h_i\)，求\(h\)有多少個字串匹配\(p\)。\(A\)匹配\(p\)指：\(A,p\)等長且將\(A\)從小到大排序后，依次為\(A_{p_1},A_{p_2},...,A_{p_n}\)。
\(n,m\leq 10^6\)。

\(Solution\)
做法1：
令\(pos[p[i]]=i\)，\(A\)匹配\(p\)，只需滿足，\(A\)和\(pos\)每個位置在前綴中的排名相等，也就是：\(\forall i\in[1,n]\)，\(A_1,...,A_{i-1}\)中小于\(A_i\)的數的個數 等于 \(pos_1,...,pos_{i-1}\)中小于\(pos_i\)的數的個數（不是\(p\)！）。
記\(a_1,...,a_{i-1}\)中小于\(a_i\)的數的個數為\(rk_i\)，兩個串的\(rk_i\)能直接比較判斷串是否相等，也可以用來定義KMP的相等：

• 對\(p\)求\(fail\)時，令\(j=fail[i-1]\)，即當前\(border\)后綴長為\(j\)，若該后綴中小于\(pos_i\)的數的個數等于當前匹配的前綴\(pos_1\sim pos_j\)中的\(rk_{j+1}\)，則\(fail[i]=j+1\)；否則\(j=fail[j]\)，當前匹配后綴縮短（\(pos_{i-j}\sim pos_{i-fail[j]-1}\)不再對之后\(rk_i\)產生貢獻）。
• 匹配時，維護當前匹配的串的\(rk\)，判斷是否與\(p\)串的\(rk\)相等。相等就\(++j\)，否則\(j=fail[j]\)，當前串縮短（且\(a_{i-j}\sim a_{i-fail[j]-1}\)不再對之后\(rk_i\)產生貢獻）。

所以就是KMP改一下判斷方式并維護當前\(rk\)。動態(tài)維護\(rk\)可以直接樹狀數組，或者麻煩點雙向鏈表。
復雜度\(O(n\log n)\)或\(O(n)\)。

做法2：
對每個\(i\)，求出\(p_i\)前面第一個比\(p_i\)小的數\(pre_{p_i}\)，及\(p_i\)后面第一個比\(p_i\)小的數\(nxt_{p_i}\)（用一個雙向鏈表）。
因為匹配的時候已確定的是\(A_1\sim A_{i-1}\)，即\(p_j=1\sim i-1\)的部分，利用這個前綴可以考慮：\(A\)匹配\(p\)，只需滿足 \(\forall i\in[1,n]\)，\(A_{pre_i}<A_i<A_{nxt_i}\)。（寫的時候可令\(pre_i=pre_i-i\)，匹配時設當前下標\(x\)，\(x+pre_i\)即當前匹配串中\(x\)對應\(pre_i\)位置）
這個東西大概是因為是相對關系，所以也可以維護\(border\)。
因為匹配是對\(p_i=1,2,3,...\)的\(p_i\)依次匹配，實際是對\(pos\)匹配而不是\(p\)。所以對\(pos\)求\(fail\)，過程中匹配與否同樣通過\(pos_{pre_i}<pos_i<pos_{nxt_i}\)決定。

所以可用KMP做，修改一下匹配的條件即可。（但感覺還是好神）

（只需對KMP的等號匹配修改一下，其它不變）復習一下KMP就兩種都寫一遍。

void GetFail(char *s)//pattern
{
	int m=strlen(s+1);
	for(int i=2,j=0; i<=m; ++i)
	{
		while(j && s[i]!=s[j+1]) j=fail[j];
		fail[i]=s[i]==s[j+1]?++j:0;
	}
}
void Match(char *p,char *s)// p 在 s 中出現的位置
{
	int j=0,n=strlen(s+1),m=strlen(p+1);
	for(int i=1; i<=n; ++i)
	{
		while(j && s[i]!=p[j+1]) j=fail[j];
		if(s[i]==p[j+1]) ++j;
		if(j==m) printf("%d\n",i-m+1);
	}
}

---

KMP：

//912ms	31.11MB
#include <bits/stdc++.h>
#define pc putchar
#define gc() getchar()
#define pb emplace_back
typedef long long LL;
const int N=1e6+5;

int P[N],pos[N],L[N],R[N],pre[N],nxt[N],A[N],fail[N];

inline int read()
{
	int now=0,f=1; char c=gc();
	for(;!isdigit(c);c=='-'&&(f=-1),c=gc());
	for(;isdigit(c);now=now*10+c-48,c=gc());
	return now*f;
}
inline bool OK(int *A,int x,int i)
{
	return A[x+pre[i]]<=A[x]&&A[x+nxt[i]]>=A[x];
//	return (!pre[i]||A[x+pre[i]]<A[x])&&(!nxt[i]||A[x+nxt[i]]>A[x]);
}

int main()
{
	const int n=read(),m=read();
	for(int i=1; i<=n; ++i) pos[P[i]=read()]=i;
	for(int i=1; i<=m; ++i) A[i]=read();
//Get Pre/Next
	for(int i=1; i<=n; ++i) L[i]=i-1, R[i]=i+1;
	R[n]=0;//
	for(int i=n; i; --i)
	{
		int x=pos[i];
		if(L[x]) pre[i]=P[L[x]]-i;
		if(R[x]) nxt[i]=P[R[x]]-i;
		L[R[x]]=L[x], R[L[x]]=R[x];
	}
//GetFail
	for(int i=2,j=0; i<=n; ++i)
	{
		while(j && !OK(pos,i,j+1)) j=fail[j];
		fail[i]=OK(pos,i,j+1)?++j:0;
	}
//Match
	std::vector<int> ans;
	for(int i=1,j=0; i<=m; ++i)
	{
		while(j && !OK(A,i,j+1)) j=fail[j];
		if(OK(A,i,j+1)) ++j==n&&(ans.pb(i-n+1),j=fail[j]);//因為判斷問題，匹配了要手動跳一次j！
	}
	printf("%d\n",ans.size());
	for(auto v:ans) printf("%d ",v); pc('\n');

	return 0;
}

KMP+樹狀數組：

//912ms	31.11MB
#include <bits/stdc++.h>
#define pc putchar
#define gc() getchar()
#define pb emplace_back
typedef long long LL;
const int N=1e6+5;

int P[N],pos[N],L[N],R[N],pre[N],nxt[N],A[N],fail[N];

inline int read()
{
	int now=0,f=1; char c=gc();
	for(;!isdigit(c);c=='-'&&(f=-1),c=gc());
	for(;isdigit(c);now=now*10+c-48,c=gc());
	return now*f;
}
inline bool OK(int *A,int x,int i)
{
	return A[x+pre[i]]<=A[x]&&A[x+nxt[i]]>=A[x];
//	return (!pre[i]||A[x+pre[i]]<A[x])&&(!nxt[i]||A[x+nxt[i]]>A[x]);
}

int main()
{
	const int n=read(),m=read();
	for(int i=1; i<=n; ++i) pos[P[i]=read()]=i;
	for(int i=1; i<=m; ++i) A[i]=read();
//Get Pre/Next
	for(int i=1; i<=n; ++i) L[i]=i-1, R[i]=i+1;
	R[n]=0;//
	for(int i=n; i; --i)
	{
		int x=pos[i];
		if(L[x]) pre[i]=P[L[x]]-i;
		if(R[x]) nxt[i]=P[R[x]]-i;
		L[R[x]]=L[x], R[L[x]]=R[x];
	}
//GetFail
	for(int i=2,j=0; i<=n; ++i)
	{
		while(j && !OK(pos,i,j+1)) j=fail[j];
		fail[i]=OK(pos,i,j+1)?++j:0;
	}
//Match
	std::vector<int> ans;
	for(int i=1,j=0; i<=m; ++i)
	{
		while(j && !OK(A,i,j+1)) j=fail[j];
		if(OK(A,i,j+1)) ++j==n&&(ans.pb(i-n+1),j=fail[j]);//因為判斷問題，匹配了要手動跳一次j！
	}
	printf("%d\n",ans.size());
	for(auto v:ans) printf("%d ",v); pc('\n');

	return 0;
}