Codeforces-914F Substrings in a String （Bitset求T串中S串出现次数）

之前有过区域赛，简化版问题：

给定一个小写字符组成的字符串S，（|S|<1e5，下标从1开始）,现在有Q种操作，对于每个操作Q(Q<=1e5)，输入opt，

如果opt==1，输入x，c，表示把S[x]改为c，（c是小写字母）。

如果opt==2，输入L，R，和字符串T，输出S[L-R]中有多少个字串==T（字符串可以重叠）,（|T|<=100）。

（其中opt==2的询问次数小于1e3）

-------------------------------------------分界线-------------------------------------

此题：

Given a string s, process q queries, each having one of the following forms:

1 i c — Change the i-th character in the string to c.
2 l r y — Consider the substring of s starting at position l and ending at position r. Output the number of times y occurs as a substring in it.

Input

The first line of the input contains the string s (1 ≤ |s| ≤ 10⁵) of lowercase English letters.

The second line contains an integer q (1 ≤ q ≤ 10⁵) — the number of queries to process.

The next q lines describe the queries and may have one of the following forms:

1 i c (1 ≤ i ≤ |s|)
2 l r y (1 ≤ l ≤ r ≤ |s|)

c is a lowercase English letter and y is a non-empty string consisting of only lowercase English letters.

The sum of |y| over all queries of second type is at most 10⁵.

It is guaranteed that there is at least one query of second type.

All strings are 1-indexed.

|s| is the length of the string s.

Output

For each query of type 2, output the required answer in a separate line.

Example

Input

ababababa
3
2 1 7 aba
1 5 c
2 1 7 aba

Output

3
1

Input

abcdcbc
5
2 1 7 bc
1 4 b
2 4 7 bc
1 2 a
2 1 4 aa

Output

2
2
1

Note

Consider the first sample case. Initially, the string aba occurs 3 times in the range [1, 7]. Note that two occurrences may overlap.

After the update, the string becomes ababcbaba and now aba occurs only once in the range [1, 7].

思路：题意和上面的差不多，不过数据更大一点，只有Bitset或者分块优化（后者我没有试过）。

具体的：1，假设我们要统计S里有多少个T，先统计S里面字符==T[0]的是哪些，然后统计S中有T[0]的位置后面跟的字符==T[1]的有哪些，然后统计S中有T[0]的位置后面跟的字符==T[1]的而且后面跟的字符==T[2]的有哪些.....直到对比到S[len-1]。

2，最后利用位移可以得到某个区间的1的个数。

for(i=;i<S;i++)

   ans&=(bitset[T[i]-'a']>>i);

ans开始全部是1； bitset是保存的T串里每个字符的位置；

（目测还有非常高效的方法，提交列表里有效率为5倍以上的，还有待学习）

#include<bitset>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

using namespace std;

const int maxn=;

bitset<maxn>s[],ans;

char a[maxn],b[maxn],c[];

void read(int &res)

{

    char c=getchar();

    while(c>''||c<'') c=getchar();

    for(res=;c>=''&&c<='';c=getchar()) res=(res<<)+(res<<)+c-'';

}

int main()

{

    scanf("%s",a+);

    int T=strlen(a+);

    int i,j,l,r,Q,opt;

    for(i=;i<=T;i++)

        s[a[i]-'a'].set(i);

    read(Q);

    while(Q--){

        read(opt);

        if(opt==){

            scanf("%d%s",&j,c);

            s[a[j]-'a'][j]=;

            s[(a[j]=c[])-'a'][j]=;

        }

        else {

            read(l); read(r);

            scanf("%s",b);

            int S=strlen(b);

            if(S>r-l+) {

                 puts(""); continue;

            }

            ans.set();

            for(i=;i<S;i++){

                ans&=(s[b[i]-'a']>>i);

            }

            printf("%d\n",(ans>>l).count()-(ans>>(r-S+)).count());

        }

    }

    return ;

}

巴特西

Codeforces-914F Substrings in a String （Bitset求T串中S串出现次数）

最新文章

热门文章