Description

給定字符串 S 和 T。
串A和串B匹配的定義改為：存在一個字符的映射，使得A應用這個映射之后等于B，且這個映射必須為一個排列。
A=121, B=313，當映射為{1->3, 2->1, 3->2}時A’=B,可以匹配
A=212, B=313，當映射為{1->1, 2->3, 3->2}時A’=B,可以匹配
A=232, B=313，當映射為{1->2, 2->3, 3->1}時A’=B,可以匹配
A=123, B=111，當映射為{1->1, 2->1, 3->1}時A’=B,但此時映射不為一個排列，不能匹配

求 S 的哪些連續子串與 T 匹配.

Input

第一行兩個整數 T(T<=3),C, 分別表示數據組數與字符集大小.
對于每組數據, 第一行兩個整數 n,m, 分別表示 S,T 的長度.
第二行 n 個整數, 第 i 個整數表示 S i .
第三行 m 個整數, 第 i 個整數表示 T i .

Output

對于每組數據輸出兩行, 第一行一個整數 k 表示匹配的個數.
第二行 k 個整數表示匹配的子串在 S 中的開始位置 (下標從 1 開始), 升序排列.

Sample Input

3 3
6 3
1 2 1 2 3 2
3 1 3
6 3
1 2 1 2 1 2
3 1 3
6 3
1 1 2 1 2 1
3 1 3

Sample Output

3
1 2 4
4
1 2 3 4
3
2 3 4

Data Constraint

對于前 10% 的數據, n,m,C ≤ 1000;
對于前 30% 的數據, n,m ≤ 100000, C ≤ 40;
對于前 60% 的數據, n,m,C ≤ 100000;
對于 100% 的數據, n,m,C ≤ 1000000.

Solution

• 由于兩個串的匹配方式是不確定的，我們需要找到一個通用的方法來匹配兩個串。

• 我們考慮處理出每個字符的前一個字符距離自己的位置 wi 。

• 如果兩個串的 w 數組相同，則兩個串可以匹配！（通用的方法！）

• 若一個字符之前沒有與之相同的字符，則其 w 值為 ?1 。

• 注意：若模式串T的某一位為 ?1 ，而匹配串S的某一位的前一字符已跨過本串，他們仍能匹配。

• 如此，我們直接做 KMP 即可，時間復雜度 O(T?N) 。

Code

#include<cstdio> #include<cstring> #include<cctype> using namespace std; const int N=1e6+5; int ws[N],wt[N],next[N],f[N]; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } inline void write(int x) {if(x>9) write(x/10);putchar(x%10+'0'); } int main() {int T=read();read();while(T--){int n=read(),m=read();memset(f,0,sizeof(f));for(int i=1;i<=n;i++){int ch=read();ws[i]=f[ch]?i-f[ch]:-1;f[ch]=i;}memset(f,0,sizeof(f));for(int i=1;i<=m;i++){int ch=read();wt[i]=f[ch]?i-f[ch]:-1;f[ch]=i;}for(int i=2,j=0;i<=m;i++){while(j && !(wt[i]==wt[j+1] || wt[j+1]<0 && wt[i]>=j+1)) j=next[j];if(wt[i]==wt[j+1] || wt[j+1]<0 && wt[i]>=j+1) j++;next[i]=j;}for(int i=1,j=f[0]=0;i<=n;i++){while(j && !(ws[i]==wt[j+1] || wt[j+1]<0 && ws[i]>=j+1)) j=next[j];if(ws[i]==wt[j+1] || wt[j+1]<0 && ws[i]>=j+1) j++;if(j==m){f[++f[0]]=i-m+1;j=next[j];}}write(f[0]),putchar('\n');for(int i=1;i<=f[0];i++) write(f[i]),putchar(' ');putchar('\n');}return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 5603. 【NOI2018模拟3.27】Xjz的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。