KMP结果TLE#5#6玄关求调
查看原帖
KMP结果TLE#5#6玄关求调
1140002
ppi_SAMA楼主2025/6/15 16:14
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
string s;
int ls;
string t[N];
int cnt;
int lt[N];
int nxt[N];
void nb(int x) {
	int j = 0;
	for (int i = 2; i <= lt[x]; i++) {
		while (j && t[x][j + 1] != t[x][i])j = nxt[i];
		if (t[x][j + 1] == t[x][i])j++;
		nxt[i] = j;
	}
}
int vis[N];
int ans;
void fugai(int x) {
	int j = 0;
	for (int i = 1; i <= ls; i++) {
		while (j && t[x][j + 1] != s[i])j = nxt[i];
		if (t[x][j + 1] == s[i])j++;
		if (j == lt[x]) {
			for (int k = i + 1 - lt[x]; k <= i; k++) {
				vis[k] = 1;
			}
			j = 0;
		}
	}
}
void check() {
	for (int i = 1; i <= ls; i++) {
		if (vis[i])ans++;
		else break;
	}
}
int main() {
	s = ' ' + s;
	while (1) {
		cin >> t[++cnt];
		lt[cnt] = t[cnt].size();

		if (t[cnt] == ".") {
			cnt--;
			break;
		}
		t[cnt] = ' ' + t[cnt];
	}
	char ss;
	while(cin>>ss){
		s+=ss;
	}
	ls = s.size();
	for (int i = 1; i <= cnt; i++) {
		nb(i);
	}
	for (int i = 1; i <= cnt; i++) {
		fugai(i);
	}
	check();
	cout << ans;
	return 0;
}
2025/6/15 16:14
加载中...