https://ac.nowcoder.com/acm/problem/15253
可以先把模式串拆分,计算出每部分,然后排序
读入模式串,匹配这两部分
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; const int maxn = 1e6 + 5; ull hs[maxn],p[maxn]; char T[maxn<<1],s[maxn]; int n; vector<ull> v; ull gethash(int i,int j){ return hs[j]-hs[i-1]*p[j-i+1]; } //查找 bool judge(int i,int j){ ull x=gethash(i,j); int id=lower_bound(v.begin(),v.end(),x)-v.begin(); if(id==v.size())return false; else return v[id]==x; } int main(){ ios::sync_with_stdio(false); p[0]=1; for(int i=1;i<maxn;i++) p[i]=p[i-1]*131; cin>>(T+1); ll len=strlen(T+1); //hs[0]=1; for(int i=1;i<=len;i++) T[i+len]=T[i]; for(int i=1;i<=2*len;i++) hs[i]=hs[i-1]*131+(T[i] - 'a' + 1); for(int i=1;i<=len;i++) v.push_back(gethash(i,i+len-1)); sort(v.begin(),v.end()); cin>>n; while(n--){ cin>>(s+1); ll lens=strlen(s+1); int cnt=0; for(int i=1;i<=lens;i++) hs[i]=hs[i-1]*131+(s[i] - 'a' + 1); for(int i=1;i+len-1<=lens;i++) if(judge(i,i+len-1))cnt++; cout<<cnt<<endl; } return 0; }
abcd循环同构 的字串 abcd bcda cdab dabc
原文链接: https://www.cnblogs.com/hazelxcf/p/12397082.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/370867
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!