首页 > 代码库 > HDU3336(KMP)
HDU3336(KMP)
#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int maxn = 1e6+7; int s[maxn];//文本串 char p[2000010];//匹配串 int next[2000010];//匹配串的next数组 void GetNext(int n) { int pLen = n; next[0] = -1; int k = -1; int j = 0; while (j < pLen)//坑点啊,模板是只求出了next[n-1],但是这题需要求next[n]。。。。。!! { //p[k]表示前缀,p[j]表示后缀 if (k == -1 || p[j] == p[k]) { ++k; ++j; next[j] = k; } else { k = next[k]; } } } int main() { #ifdef xxz freopen("in.txt","r",stdin); #endif // xxz int Case; cin>>Case; while(Case--) { int n,m; cin>>n; cin>>p; int ans = 0; GetNext(n); for(int i = 1; i <= n; i++) { if(next[i] > 0) ans++; if(ans >= 10007) ans %= 10007; } ans += n; ans %= 10007; cout<<ans<<endl; } return 0; }
HDU3336(KMP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。