本文共 851 字，大约阅读时间需要 2 分钟。

【题意】

给定一个字符串s(1e5)，q(1e5)次操作，操作1给定位置i和字母c，把第i个元素替换为c；操作二先给一个0再给一个字符串t，查询字符串t在s中的出现次数。

【题解】

显然常规做法行不通，考虑STL中的Bitset 。

bitset存储二进制数位，从右往左依次为2^0,2^1,2^2,...

for(int i=0;i

如果s[]="abaaa"， N=10，那么对于a:B[0]=0000011101，对于b:B[1]=0000000010.

那么对于一个给定的字符串t，我们可以对于首字母的每个位置开始，即B[t[0]-'a']所有为1的二进制位，依次对下一个字母t[i]进行与(&)操作，以更新状态 --- 以首字母的每个位置开始的长度为l的子串是否为t，最后用count函数求出我们计算过程中的tmp的所有二进制位上1的个数即为满足要求的子串个数。

【代码】

#include 
   
    using namespace std;const int N=4e5+7;bitset 
    
      B[26];char s[N],t[N];int main(){    int n,q;    while(~scanf("%d%d",&n,&q)){        scanf("%s",s);        for(int i=0;i<26;i++) B[i].reset();        for(int i=0;i
     
       tmp=B[t[0]-'a']; //t[0]元素的位置的分布二进制                for(int i=1;i
      
       >i; //确认以每一个t[0]元素为起始点的下一位位置元素是否存在                printf("%d\n",tmp.count()); //返回tmp中1的二进制位的个数            }        }    }    return 0;}
      
     
    
   

转载地址：http://vhfen.baihongyu.com/