列表

详情


NC54661. [模板]后缀自动机

描述

这是一道模板题:给定两个字符串S和T,询问S中是否存在一个后缀P,使得T的任何一个前缀的字典序都大于P
注意:数据里同时含有大写与小写字母,比较字典序时严格按照 Ascii 编码进行比较,即我们认为 A<B<C..<Z<a<b<c<...<z 

输入描述

每组数据有两行只包含英文字母的字符串,第一行是S,第二行是T 

输出描述

每组数据输出一行,若存在这样的P,输出“YE5”,否则输出“N0”(不带引号)。

示例1

输入:

3
lglg  
rzynb  
zzytql  
dalaoddw  
uiyouivyziuoxcovzuncuiasdaisdb  
yzvuihouvsfvdjsausnnuncvviasudalsky 

输出:

YE5 
N0 
YE5

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 282ms, 内存消耗: 7192K, 提交时间: 2019-11-19 13:53:20

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

int main(){
	int T; cin >> T;
	string s, t;
	while(T--){
		bool yes = 0;
		cin >> s >> t;
		for(int i = 0; i < s.length(); ++i){
			if(s[i] < t[0]) yes = 1;
		}
		if(yes) puts("YE5");
		else puts("N0");
	}
}

C++11(clang++ 3.9) 解法, 执行用时: 242ms, 内存消耗: 984K, 提交时间: 2020-02-16 20:06:10

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int T;
	cin>>T;
	string s,t;
	while(T--)
	{
		bool yes=0;
		cin>>s>>t;
		for(int i=0;i<s.length();++i)
		{
			if(s[i]<t[0]) yes=1;
		}
		if(yes) puts("YE5");
		else puts("N0");
	}
}

上一题