[小专题]另一种字符串匹配的思路——Shift-And算法

时间：2021-07-26 17:53:20
  • 吐槽：前两天打组队赛遇到一个字符串的题考了这个（见：http://acm.hdu.edu.cn/showproblem.php?pid=5972 ）

    当时写了个KMP瞎搞然后TLE了（害），赛后去查了许多资料似乎就看见一个题考了这么个鬼东西…

问题给出

  • 给一个主串\(S=s_1s_2...s_n\)和一个模式串\(T=(t_{11}|t_{12}|...|t_{1k_1})(t_{21}|t_{22}|...t_{2k_2})...(t_{m1}|t_{m2}|...|t_{mk_m})\)，对于\(S\)的一个子串\(S'[1,m]=S[i,i+m-1]\)，只要第\(j\)个位置满足\(S[j]=t_{j1},t_{j2},..t_{jk_j}\)中的其中一个，就算匹配成功。找到\(S\)中所有能和\(T\)匹配的子串。
  • \(|S|,|T|\)的范围依然很大，\(k_i\)和字符集比较小

问题分析

  • 首先想到的是去修改一下KMP里匹配成功的条件…如果在一个位置发现了失配，即\(s[i]\not\subset t[j+1]\)，那样我们希望仍然有一个合适的失配数组\(nxt[]\)让我们跳回合适的位置，即找到一个\(T[1,j]\)的最长公共前后缀跳回去，但是这里就出现了问题，如果要保证\(S\)匹配到的后缀要和新的\(T\)的前缀匹配，那就得保证我们找的\(T\)的这个前缀包含了\(T\)的后缀，可是这样就也要改掉\(nxt[]\)数组的求解。
  • 好那就改吧，构造失配数组的时候把匹配条件t[i]==t[j+1] 改成包含关系，即我们要让\(T[1,j+1]\)这个前缀包含\(T[i-j,i]\)这个后缀如果\(k_i\)小的话这一步仍然可以认为是\(O(1)\)的时间，整个处理过程仍然是\(O(|T|)\)的。嗯到这里感觉都不错，接下来进行两个字符串的匹配了，\(S\)和\(T\)的比较也改成比较是否包含。如果失配的话同样是\(j=nxt[j]\)地往回跳，一直到\(j==|T|\)匹配成功…到这里似乎都没什么问题
  • 但是但是…一旦匹配成功输出结果，\(j\)这个指针该怎么跳？\(j=nxt[j]\)？但是很快就会发现这里这样做会漏掉一些情况…（因为如果要求【跳到的前缀包含了当前的后缀】这样一个苛刻的条件，那样可能会出现\(S\)串马上又可以匹配，但是我们条件太苛刻跳过了的情况）
  • 想来想去没法解决这个问题…
  • 好吧既然KMP没法解决…不如我们换个算法（逃

另一种字符串匹配方法

和其他算法问题一样，我们可以考虑换一个维护的对象。下标，字符集…

比如这里，我们考虑从另一个角度切入字符串匹配的问题：对于字符集比较小的匹配，对模式串\(T\)里每个字符出现的位置进行记录：即用一个数组\(B[i][j]\)表示字符\(i\)在第\(j\)个位置是否出现。这样记录能够处理这题里令我们头疼的问题：模式串的一个位置允许多种取值。

朴素暴力

好了现在有了这么一个想法，先试试看最暴力地要怎么做这个问题

（约定|S|=m,|T|=n）

\(O(n)\)地求出\(B[][]\)数组

for(int i=1;i<=n;i++)

	int k;scanf("%d",&k);

    for(int j=1;j<=k;j++)

		int t;scanf("%d",&t);

		B[t][i]=1

每次暴力匹配\(S\)和\(T\)，时间复杂度还是\(O(nm)\)

for(int i=1;i<=m;i++)

    int j=1;

	for(;j<=n&&B[s[i+j-1]][j];j++);

    if(j==n+1)

    	match!

优化算法

和其他字符串算法的思路一样，我们尝试能不能通过维护一些前后缀的信息来减少信息的冗余：比如这里我们发现，上面的算法每次都在暴力\(O(n)\)地比较\(S[i,i+n-1]\)和\(T[1,n]\)，我们可以把这个过程看成\(S[1,i+n-1]\)的后缀和\(T[1,n]\)的前缀进行比较，于是类似KMP的思路，也许我们可以去维护\(S\)的后缀和\(T\)的前缀相关的信息！（这就是Shift-And算法的思路！）

我们考虑再用一个数组\(D[]\)来维护这样一个信息：\(D[j]=1\)当且仅当\(S[i-j+1,i]\)和\(T[1,j]\)匹配，即\(S\)的一个后缀是\(T\)的前缀。否则\(D[j]=0\)。马上我们将会发现用Bool类型储存这样一个信息的优越性。

如果我们让\(i,j\)两个指针一起跑（如图），能写出递推式：\(D[j+1]=(D[j])\&(S[i+1]==T[j+1])\)。进一步我们利用前面做好的数组\(B[][]\)，可以把相等的判定修改一下，变成：\(D[j+1]=D[j]\&B[S[i+1]][j+1]\)

[小专题]另一种字符串匹配的思路——Shift-And算法

到这里都还只是逐位地进行位运算的比较，但是我们注意到这个\(D[]\)似乎可以做成一个\(bitset\)，把它看成是一个长度为\(|T|\)的二进制数的话，尝试直接用一个\(D\)表示这个数组，用位运算来实现这个递推。

考虑上面的过程，从\(D[j]\)到\(D[j+1]\)需要先把上一位\(D[j]\)的信息复制过来，再对\(j+1\)位进行一个取\(\&\)的操作，考虑从\(i=1,j=1\)往上递推的整个过程…对于每个\(i\)，每次遍历\(1,2,3,...,j...,|T|\)，复制信息…对应位置取\(\&\)，这个复制信息的过程不就相当于把一个二进制数全部左移一位么？每次取\(\&\)也很麻烦，我们把\(B[i][j]\)的第二个维度也压掉，直接对两个二进制数按位\(\&\)，同时为了保证\(\&\)正确性，每次左移完了之后把最低位赋为1。

另外，对于超过\(|T|\)的\(j\)的信息我们可以直接丢掉，所以也不用担心丢失什么信息。

至此，我们已经可以抛去\(j\)这个指针，得到从\(i\)到\(i+1\)递推式：

\(D=(D<<1|1)\&B[S[i+1]]\)实现

核心代码

const int N=5000005;

const int M=1005;

char s[N];

char t[M];

bitset<M>B[10],D;

int n,len;

int main(){

	scanf("%d",&n);

	rep(i,1,n){

		int k;scanf("%d",&k);

		rep(j,1,k){

			int t;scanf("%d",&t);

			B[t].set(i,1);

		}

	}

	scanf("%s",s+1);

	len=strlen(s+1);

	rep(i,1,len){

		D=(D<<1).set(1)&B[s[i]-'0'];

		if(D[n]){

			char ch=s[i+1];

			s[i+1]=0;

			puts(s+i-n+1);

			s[i+1]=ch;

		}

	}

    return 0;

}

参考资料

相关文章