Shift-And算法

2021/7/20 22:06:33

本文主要是介绍Shift-And算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

先看一道例题:regular number

 

简要题意: 

我们有一个长度为$n$的模式串,其中的每一位有多种可能。

我们还有一个长度不超过5*106的主串。

问,有哪些模式串在主串中出现过,输出这些模式串。

分析: 

这道题我们可以理解为有多个模式串,要看每个模式串能否与主串匹配。

很显然的是,我们难以用$kmp$来解决多个模式串问题。

我们引入一个新的知识点:Shift-And算法 

 

Shift-And算法: 

运行方式:我们先给出算法运行的方式。(先令只有一个模式串)

先说明,我这里用的$mp$以及$D$都是bitset。

模式串一共1~n位,其中第i位为x,那么我们令mp[x][i-1]=1(模式串第i位为x是可行的)

接下来呢,我们一位一位地加入主串。

我们现在加到了第i位,主串的第i位为S[i]。

让先后让 D <<= 1, D |= 1, D=D&mp[S[i]]

我们不停滴进行上列操作,若加入了$k$位主串,且$D[n-1]==1$时,我们找到了匹配。

那么匹配的内容为S[i-n+1]+S[i-n+2]+...+S[i]

 

举例:  

模式串为 2 2 3,主串为 1 2 3 2 2 3 2 2 3

mp[1] = {000}
mp[2] = {011}
mp[3] = {100}
D初始为0

1.加入S[1]
D<<=1;D|=1;  {001} 
D&=mp[1];    {000}

2.加入S[2]
D<<=1;D|=1;  {001}
D&=mp[2];    {001}

3.加入S[3]
D<<=1;D|=1;  {011}
D&=mp[3];    {000}

4.加入S[4]
D<<=1;D|=1;  {001}
D&=mp[2];    {001}

5.加入S[5]
D<<=1;D|=1;  {011}
D&=mp[2];    {011}

6.加入S[6]
D<<=1;D|=1;  {111}
此时我们的D的最高位为1
所以我们得到匹配S[4~6]代码#include<bits/stdc++.h>
using namespace std;
#define re register int
bitset<10>mp[100],D;
int S[100];
signed main()
{
    int n,m;cin>>n>>m;
    for(re i=1,x;i<=n;++i)cin>>x,mp[x][i-1]=1;
    for(re i=1;i<=n;++i)cout<<mp[i]<<endl;
    for(re i=1;i<=m;++i)cin>>S[i];
    
    for(re i=1;i<=m;++i)
    {
        D<<=1;D|=1;
        D=D&mp[S[i]];
        if(D[n-1]==1)cout<<i+1-n<<endl;
    }
}
输入:
3 10
2 2 3
1 2 3 2 2 3 2 2 3 1
输出:
4
7

原理: 

这里的原理kzsn悟了很久,但可能不是很清晰,望读者自己多举几个例子来结合

相信大家发现,我们的mp在bitset中其实是反着的。

这有利于我们判断。

我们主串已经加入i位,D[x]为1表示:目前,主串的[i-x+1~i]位,与模式串前x+1项相同。

接下来我们会加入主串的i+1位S[i+1],D进行操作后,若D[x+1]也为1

 

 

 



这篇关于Shift-And算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程