萌新刚学 OI,ACAM 60pts 求助
查看原帖
萌新刚学 OI,ACAM 60pts 求助
556000
Mrkn_chenyx12楼主2023/9/21 17:15

求助大佬,可送关

Subtask1 除最后两个点外均 AC。

#7: Wrong Answer.
    wrong answer On line 1 column 1,
    read 2, expected 5.
#8: Wrong Answer.
    wrong answer On line 1 column 1,
    read 1, expected 4.

另外,Subtask2 已全部 TLE,咋个状压法求教,没太看懂。

代码:

#include <bits/stdc++.h>
using namespace std;

struct Node {
	bool sucs;
	int sub[26];
	int fa, fail, dep;
}t[1024];

int n,m, cnt;

char wd[32][32], docm[2000024];
bool sf[2000024];

inline int len(char *str) {
	int ret = 0;
	while(str[ret]) ret++;
	return ret;
}

inline int get_fail(int nid, int ch) {
	nid = t[nid].fa;
	while(nid && !~t[t[nid].fail].sub[ch]) {
		nid = t[nid].fa;
	}
	return nid == 0 ? 0 : t[t[nid].fail].sub[ch];
}

int main() {
	scanf("%d %d", &n, &m);
	t[0].sucs = false;
	for(int i = 0; i<26;i++) t[0].sub[i]=-1;
	t[0].fail = 0;
	t[0].fa = 0;
	t[0].dep = 0;
	int wnodes[32],depths[32];
	int max_depth = 0;
	for(int i=0; i<n;i++) {
		scanf("%s", wd[i]);
		depths[i] = len(wd[i]);
		wnodes[i] = 0;
		if(depths[i] > max_depth) max_depth = depths[i];
	}
	int d;
	for(int i = 0; i<max_depth; i++) {
		for(int j=0; j<n;j ++) if(i < depths[j]) {
			d = wnodes[j];
			if(!~t[d].sub[wd[j][i]-'a']) {
				t[d].sub[wd[j][i]-'a']=++cnt;
				t[cnt].sucs = false;
				for(int k = 0;k<26;k++) {
					t[cnt].sub[k] = -1;
				}
				t[cnt].fa = d;
				t[cnt].fail = get_fail(cnt, wd[j][i]-'a');
				t[cnt].dep = t[d].dep + 1;
			}
			d = t[d].sub[wd[j][i]-'a'];
			wnodes[j] = d;
		}
	}
	for(int i=0;i<n;i++) t[wnodes[i]].sucs=true;
	for(int i=0;i<m;i++) {
		scanf("%s", docm);
		int d = 0, wl = len(docm), ans = 0, xd;
		for(int j = 0; j < wl; j++) {
			while(!~t[d].sub[docm[j]-'a'] && d) {
				d = t[d].fail;
			}
			if(~t[d].sub[docm[j]-'a']) {
				d = t[d].sub[docm[j] - 'a'];
			}
			xd = d;
			sf[j] = false;
			while(~xd) {
				if(t[xd].sucs) {
					if(t[xd].dep == j + 1) {
						sf[j] = true;
						ans = j+1;
					} else if(sf[j - t[xd].dep]) {
						sf[j] = true;
						ans = j+1;
					}
				}
				if(xd == 0) break;
				xd = t[xd].fail;
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}
2023/9/21 17:15
加载中...