WA 10 且都不是 -1
查看原帖
WA 10 且都不是 -1
756660
B612Dusk楼主2023/8/22 16:43

一共 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;
}

悬关

2023/8/22 16:43
加载中...