Acwing周赛42 (KMP，偷偷拿字符串哈希水过去了)

桃扇骨 2023-09-30 09:25 76阅读 0赞

[题目][Link 1]  
**题意:** 分别给出长度为n和m的字符串a、b，有q次询问，询问在字符串a的\[l,r\]中出现了多少次b。  
**思路:** KMP匹配一下，然后维护一下前缀和，即可O(1)查询。  
**时间复杂度:** O(n+q)  
**代码:**

// Problem: 出现次数
    // Contest: AcWing
    // URL: https://www.acwing.com/problem/content/4315/
    // Memory Limit: 256 MB
    // Time Limit: 1000 ms
    // 
    // Powered by CP Editor (https://cpeditor.org)
    
    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<complex>
    #include<cstring>
    #include<cmath>
    #include<vector>
    #include<map>
    #include<unordered_map>
    #include<list>
    #include<set>
    #include<queue>
    #include<stack>
    #define OldTomato ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
    #define fir(i,a,b) for(int i=a;i<=b;++i) 
    #define mem(a,x) memset(a,x,sizeof(a))
    #define p_ priority_queue
    // round() 四舍五入 ceil() 向上取整 floor() 向下取整
    // lower_bound(a.begin(),a.end(),tmp,greater<ll>()) 第一个小于等于的
    // #define int long long //QAQ
    using namespace std;
    typedef complex<double> CP;
    typedef pair<int,int> PII;
    typedef long long ll;
    // typedef __int128 it;
    const double pi = acos(-1.0);
    const int INF = 0x3f3f3f3f;
    const ll inf = 1e18;
    const int N = 2e5+10;
    const int M = 1e6+10;
    const int mod = 1e9+7;
    const double eps = 1e-6;
    inline int lowbit(int x){ return x&(-x);}
    template<typename T>void write(T x)
    {
        if(x<0)
        {
            putchar('-');
            x=-x;
        }
        if(x>9)
        {
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T> void read(T &x)
    {
        x = 0;char ch = getchar();ll f = 1;
        while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
        while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
    }
    int n,m,k,T;
    int q;
    char s[1002];
    char p[1002];
    int ne[1002];
    int a[1002];
    void solve()
    {
       ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
       cin>>n>>m>>q;
       cin>>(s+1); cin>>(p+1);
       for(int i=2,j=0;i<=m;++i)
       {
       	  while(j && p[i] != p[j+1]) j = ne[j];
       	  if(p[i] == p[j+1]) j++;
       	  ne[i] = j;
       }
       for(int i=1,j=0;i<=n;++i)
       {
       	  while(j && s[i] != p[j+1]) j = ne[j];
       	  if(s[i] == p[j+1]) j++;
       	  if(j == m)
       	  {
       	  	 a[i-j+1] = 1;
       	  	 j = ne[j];
       	  }
       }
       // fir(i,1,n) cout<<i<<":"<<a[i]<<endl;
       for(int i=1;i<=n;++i) a[i] += a[i-1];
       while(q--)
       {	
       	  int l,r; cin>>l>>r;
       	  if(r-l+1 < m) {cout<<0<<"
    "; continue;}
       	  cout<<a[r-m+1] - a[l-1]<<"
    ";
       }
    }
    signed main(void)
    {  
       T = 1;
       // OldTomato; cin>>T;
       // read(T);
       while(T--)
       {
       	 solve();
       }
       return 0;
    }

[Link 1]: https://www.acwing.com/problem/content/description/4315/