啊?求调
查看原帖
啊?求调
747369
CooooldWind_楼主2023/10/31 20:03

rt,调了几十次了(尊嘟没在滥用评测机资源qwq),这份是90pts的码AC+WA,chk数组的120开大了会变成MLE+WA,然后再大一点就MLE+AC。

就,挺抽象的(

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

int n,m,nxt[500100][26],lcnt = 0;
bool chk[500100][120];

int trans(char c){return c - 'a';}

void insert(string s,int word_num){
	int pos = 0;
	for(int i = 0;i < s.length();i++){
		if(nxt[pos][trans(s[i])] != 0){
			pos = nxt[pos][trans(s[i])];
		}
		else{
			lcnt++;
			nxt[pos][trans(s[i])] = lcnt;
			pos = lcnt;
		}
	}
	chk[pos][word_num] = true;
	return;
}

void check(string s){
	int pos = 0;
	for(int i = 0;i < s.length();i++){
		if(nxt[pos][trans(s[i])] == 0){
			cout << endl;
			return;
		}
		pos = nxt[pos][trans(s[i])];
	}
	bool flag = false;
	for(int i = 1;i <= n;i++){
		if(chk[pos][i]){
			if(flag) cout << " ";
			else flag = true;
			cout << i;
		}
	}
	cout << endl;
	return;
}

int main(){
	cin >> n;
	for(int i = 1,j;i <= n;i++){
		cin >> j;
		while(j--){
			string str;
			cin >> str;
			insert(str,i);
		}
	}
	cin >> m;
	for(int i = 1;i <= m;i++){
		string s;
		cin >> s;
		check(s);
	}
	return 0;
}
2023/10/31 20:03
加载中...