一共 70 个点, WA了 10 个,WA 在 11, 25这些测试点,dalao求调, 码风不是太丑陋
#include<bits/stdc++.h>
#define N 4000010
#define reg register
#define eps 0.00000005
#define mod 100005
#define int long long
using namespace std;
//char in[1 << 20] ,*ss = in,*tt = in;
//#define getchar() (tt == ss && (tt = (ss = in) + fread(in, 1, 1 << 20,stdin),ss == tt) ? EOF : *ss++)
inline int read(){
int x = 0, f = 1; char ch = getchar();
while(ch > '9' || ch < '0'){
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
char s[N], t[N];
int len_s, len_t, S, nxt[N], ans1, ans2, ans3;
inline void ex_S()
{
for(reg int i = len_s + 1; i <= len_s + S; i = -~i)
s[i] = s[i - len_s];
len_s += S;
}// S 串自身复制一遍
inline void KMP_pre()
{
for(reg int i = 2, j = 0;i <= len_t;i = -~i)
{
while(j && t[i] == t[j + 1]) j = nxt[j];
if(t[i] == t[j + 1]) j ++;
nxt[i] = j;
}
}// 传统处理 nxt
inline int KMP()
{
int ans = 0, maxx = 0;
for(reg int i = 1, j = 0;i <= len_s;i = -~i)
{
if(s[i] != t[j + 1]) maxx = max(maxx , ans), ans = 0; // 失配了
while(j && s[i] != t[j + 1]) j = nxt[j]; // 失配
if(s[i] == t[j + 1]) j ++;
if(j == len_t) ans ++, j = 0;
}
maxx = max(maxx, ans);
return maxx;
} // 传统但是多了一个失配时的考虑
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
scanf("%s", s + 1), len_s = S = strlen(s + 1);
scanf("%s", t + 1), len_t = strlen(t + 1);
while(len_s <= len_t) ex_S();
KMP_pre();
ex_S(), ans1 = KMP();
while(len_s <= (len_t << 1)) ex_S();
ex_S() , ans2 = KMP(); // 扩至少 t 的二倍是为了判断 -1
if(ans2 > ans1) puts("-1");
else printf("%d", ans1);
return 0;
}
悬关