2019河南ICPC省赛：DNA序列---复制问题【KMP的简单模板题】

由于数据弱，可以暴力。
题目链接点击这里
本题需要注意 回文串特判问题
本文给出的是KMP代码：

#include 
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f
ll nt[inf];
ll lent, lens, cnt;
string s,t;
bool pad()
{for(ll i=0;i<lent/2;i++){if(t[i]!=t[lent-i-1]) return false;}return true;
}
void Next()
{ll i=0;ll j=-1;nt[0]=-1;while(i<lent){if(j==-1||t[i]==t[j]){i++;j++;nt[i]=j;}else j=nt[j];}return;
}
void kmp()
{ll i=0;ll j=0;Next();while(i<lens){if(j==-1||s[i]==t[j]){i++;j++;}else j=nt[j];if(j==lent) cnt++;}
}
int main(void)
{ll n;cin>>n;while(n--){cnt=0;cin>>t>>s;lent=t.size();lens=s.size();kmp();if(!pad()){reverse(s.begin(),s.end());kmp();}cout<<cnt<<endl;}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！