[小专题]另一种字符串匹配的思路——Shift-And算法
阅读原文时间:2023年07月08日阅读:1
  • 吐槽:前两天打组队赛遇到一个字符串的题考了这个(见: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]\)

到这里都还只是逐位地进行位运算的比较,但是我们注意到这个\(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;
}

参考资料