KMP50分,绷不住了
查看原帖
KMP50分,绷不住了
546830
XSean楼主2023/5/9 10:06
#include <bits/stdc++.h>

#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define pre(i, a, b) for(int i = (a); i >= (b); i--)
#define Ede(i, u) for(int i = h[u]; i; i = ne[i])
#define go(i, a) for(auto i : a)
//#define int long long
#define LL long long
#define ULL unsigned long long
#define PII pair<int, int>
#define PIL pair<int, long long>
#define PLI pair<long long, int>
#define PLL pair<long long, long long>
#define mp make_pair
#define eb emplace_back
#define opb pop_back
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define sf scanf
#define prf printf
#define el putchar('\n')
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define mmc(arr1, arr2) memcpy(arr1, arr2, sizeof(arr2))
#define Db(x) prf("test: %s ", x)
const int inf = 0x3f3f3f3f;

template <typename T> inline void rd(T &x){
	x = 0; bool f = true; char ch = getchar();
	while(ch < '0' || ch > '9'){ if(ch == '-') f = false; ch = getchar();}
	while(ch >= '0' && ch <= '9'){ x = (x << 1) + (x << 3) + (ch ^ '0'); ch = getchar();}
	if(!f) x = -x;
}
template <typename T, typename ...Args> inline void rd(T &x, Args &...args){ rd(x); rd(args...);}

using namespace std;

const int N = 1e6 + 10;
char p1[N], p2[N];
char s[N];
int ne1[N], ne2[N];
int l1, l2;
bool check(int idx){
	if(s[idx + 1] == '#' && s[idx - l1] == '#') return true;
	else return false;
}
int main(){
	/*
	freopen(".in", "r", stdin);
	freopen(".out", "w", stdout);
	*/
	sf("%s", p1 + 1); getchar();
	rep(i, 1, strlen(p1 + 1)) p2[i] = p1[i];
	p2[1] = (p1[1] >= 'a') ? (p1[1] - 'a' + 'A') : (p1[1] - 'A' + 'a');
	cin.getline(s + 1, N);
	rep(i, 1, strlen(s + 1)){
		if(s[i] == ' ') s[i] = '#';
	}
	l1 = strlen(p1 + 1), l2 = strlen(s + 1);
	s[0] = s[l2 + 1] = '#';
	for(int i = 2, j = 0; i <= l1; i++){
		while(j && p1[i] != p1[j + 1]) j = ne1[j];
		if(p1[i] == p1[j + 1]) j++;
		ne1[i] = j;
	}
	for(int i = 2, j = 0; i <= l1; i++){
		while(j && p2[i] != p2[j + 1]) j = ne2[j];
		if(p2[i] == p2[j + 1]) j++;
		ne2[i] = j;
	}
	int idx = N, f = 1, cnt = 0;
	for(int i = 1, j = 0; i <= l2; i++){
		while(j && s[i] != p1[j + 1]) j = ne1[j];
		if(s[i] == p1[j + 1]) j++;
		if(j == l1 && check(i)){
			if(f){
				f = 0;
				idx = i - l1;
			}
			j = ne1[j];
			cnt++;
		}
 	}
 	f = 1;
 	for(int i = 1, j = 0; i <= l2; i++){
		while(j && s[i] != p2[j + 1]) j = ne2[j];
		if(s[i] == p2[j + 1]) j++;
		if(j == l1 && check(i)){
			if(f){
				f = 0;
				idx = min(idx, i - l1);
			}
			j = ne2[j];
			cnt++;
		}
 	}
 	if(!cnt) puts("-1");
 	else prf("%d %d\n", cnt, idx);
 	
	return 0;
}





2023/5/9 10:06
加载中...