本地能过,但oj上tle(玄关)
查看原帖
本地能过,但oj上tle(玄关)
1149844
floatingincodes楼主2024/9/12 22:15
#include<iostream>
#include<sstream>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<unordered_map>
#include<unordered_set>
#include<cmath>
using namespace std;
const int N = 200010;
vector<string> mp;
string s, tmp;
bool f[N];
int pos=0;
inline bool check(int x) {
	for (int i = 0; i < mp.size(); i++) {
		int t = mp[i].size();
		if (x - t >= 0 && f[x - t] && s.substr(x - t + 1, t) == mp[i]) {
			f[x] = 1;
			//cout << mp[i] << ' ' << x << ' ' << s.substr(x - t + 1, t) << endl;
			return 1;
		}
	}
	//for(int i=1;i<=s.size();i++) cout << f[i] << ' ';
	//cout << endl;
	return 0;
}
int main()
{
	getline(cin, s);
	while (s != ".") {
		stringstream ssin(s);
		while (ssin >> tmp) mp.push_back(tmp);
		getline(cin, s);
	}
	s=" ";
	while (cin >> tmp) s += tmp;
	//cout << s << endl;
	f[0] = 1;
	for (int i = 1; i < s.size(); i++) {
		if (check(i)) pos = i;
	}
	cout << pos;
}
2024/9/12 22:15
加载中...