HDU - 1686(KMP)

刷都可以刷

HDU - 1686

题意：

给你一个字符串$a$，一个字符串$b$，问$a$在$b$中出现了多少次。

题解：

直接上$KMP$，只需要在匹配的时候，每当遍历到模式串的长度答案+1，然后更新下标即可。

//I am so vegetable
//#define err
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define FIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define _for(type,i,a,b) for(type i = (a);i<(b);++i)
#define endl '\n'


const int N=1e4+5;
int nx[N];
void gn(string s){
  int i=0,j=-1;
  nx[0]=-1;
  while(i<s.size()){
    if(j==-1||s[i]==s[j])++i,++j,nx[i]=j;
    else j=nx[j];
  }
}
int kmp(string t,string s){
  int i=0,j=0,ans=0;
  while(i<t.size()){
    if(j==-1||t[i]==s[j])++i,++j;
    else j=nx[j];
    if(j==s.size())++ans,--i,j=nx[j-1];
  }
  return ans;
}
signed main() {
  FIO;
  int T;cin>>T;
  while(T--){
    string s,t;cin>>s>>t;
    gn(s);
    cout<<kmp(t,s)<<endl;
  }
  return 0;
}

• 本文作者： baddog
• 本文链接： https://katoli.github.io/2020/11/13/HDU-1686-KMP/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！